[이코테] DFS & BFS - 미로 탈출

못 풀었다. DFS와 BFS는 정말 머리 속에 안 들어와,,,

심지어 이번 문제는 BFS로 풀어야 하는데 DFS로 풀려고 했음

 

 

1. 내 풀이

ㅋㅋㅋㅋ 이걸 풀었다고 할 수 있을까...?

n, m = map(int, input().split())

# 미로 만들기
graph = []
for i in range(n):
    for j in range(m):
        graph.append(list(int(input())))

def dfs(x, y):
    if graph[x][y] == 1:
        graph[x][y] = 0
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
    else:
        return False

def visited():
    if

 

1-1. 풀이 도중 생각

1) 이건 dfs일까 bfs일까? 우선 가던 길을 하나 쭉 계속 가야 하니까 dfs로 해야 하는거 아닐까?

2) 정확히 (n,m)에 도착하게 한다는게 이전에 풀었던 예시들과 이 문제가 다른 점인 것 같다

3) 시작이 무조건 (1,1)이고, 처음에는 오른쪽이나 아래쪽으로만 움직일 수 있다 (근데 사선으로는 못 움직이나?) 

 

 

2. 정답

from collecitons import deque

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]

# BFS
def bfs(x,y):
	queue = deque()
	queue.append((x,y))
	while queue:
	x, y = queue.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
        if graph[nx][ny] == 0:
        	continue
        if graph[nx][ny] == 1:
        	graph[nx][ny] = graph[x][y] + 1
            queue.append((nx,ny))
	return graph[n-1][m-1]
 
 print(bfs(0,0))

 

 

3. 새로 공부하게 된 것 or 새삼 다시 알게 된 것

1) 최단 거리 문제에서는 BFS가 유리함. DFS로 할 경우 답은 찾을 수 있으나 그것이 최단인지는 보장 X. 하지만 BFS의 경우 현재 노드에서 가까운 곳부터 찾음. 가장 가까운 것들을 계속 선택한다는 것은 곧 최단 거리를 찾아간다는 것