[샛길공부] DFS와 BFS 문제풀기 (feat. 이코테 유튜브강의)

---

영상 00:42:43 부터 시작되는 문제풀이!

* 강의 채널 : 동빈나

* 강의 이름 : (이코테 2021 강의 몰아보기) 3. DFS & BFS

* 강의 링크 : https://youtu.be/7C9RgOcvkvo 

---

 🧵 문제 1. 음료수 얼려먹기

---

 ❗ DFS 이용 문제풀이

# 첫째줄 세로n,가로m 입력받기
n, m = map(int,input().split())
 
# 둘째줄~ 입력값 리스트로 만들어 맵 만들기
graph=[ ]
for i in range(n):
    graph.append(list(map(int,input())))
 
def dfs(x,y):
    if x<=-1 or y<=-1 or x>=n or y>=m: #맵 안에서 찾을 수 있게 제한
        return False
    if graph[x][y]==0:  #조건: 방문하지 않아서 False 0이라면
        graph[x][y]=1   #조건: 방문한 증표로 True 1로 기록
        dfs(x-1,y)  #왼쪽
        dfs(x+1,y)  #오른쪽  
        dfs(x,y-1)  #아래
        dfs(x,y+1)  #위
        return True
 
result=0  #방문한 곳 체크 하기 위해 result 만들기
for i in range(n):  #세로길이 반복
    for j in range(m):  #가로길이 반복
        if dfs(i,j) ==True: #조건: 방문해서 True 1이라고 한다면
            result+=1   #방문된 곳을 체크하기위해 카운트
print(result)

---

 🧵 문제 2. 미로 탈출

---

 ❗  BFS 이용 문제풀이

<div c# 첫째줄 세로,가로 입력받기
n, m = map(int, input().split())
 
# 둘째줄~ 입력값 리스트로 만들어 맵 만들기
graph=[]
for i in range(n):
    graph.append(list(map(int,input())))
 
dx=[-1,1,0,0] #왼쪽/오른쪽/-/-
dy=[0,0,-1,1] #-/-/아래/위
 
#큐 표현을 위해 deque 라이브러리 사용!
from collections import deque  
def bfs(x,y):
    que= deque()
    que.append((x,y)) #x,y 같이 입력 
    
    while que: #큐가 빌때까지 반복하기
        x,y=que.popleft() #실행할 점을 하나씩 빼오기
        for i in range(4): #현재 지점에서 상하좌우 확인
            nx= x + dx[i] #왼쪽/오른쪽/-/-
            ny= y + dy[i] #-/-/아래/위
            if nx<0 or ny<0 or nx>=n or ny>=m: #맵 안에서 찾을 수 있게 제한
                continue    #for문으로
            if graph[nx][ny]==0: #괴물이 있는 곳
                continue    #for문으로
            if graph[nx][ny]==1: #괴물 없고, 처음 방문하는 곳
                graph[nx][ny] = graph[x][y] + 1 #이동거리를 표시하기위해 1 더하기
                que.append((nx,ny)) # 그 다음 이동을 위해 que에 집어 넣기
    return graph[n-1][m-1]  #가장 오른쪽 아래까지 도착했을때 더했던 값을 반환
    #n-1 m-1로 표기한 이유는, n과m은 자연수여서 1부터 시작 (1,2,3....)
    # 리스트 graph는 리스트여서 0부터 시작(0,1,2.....)print(result)

---

 

🧐공부 한줄 평 : 1260번 백준 문제 풀이를 시작해볼까나?? 나중에 확장해서 문제풀이를 해야겠당