1001 알고리즘

DFS와 자주 등장하는게 BFS이다. BF는 Breath First Search , 너비 우선 탐색이다. 가까운 노드부터 탐색한다. DFS는 깊이니까 최대한 벌리 있는 노드를 우선으로 탐색하는 방식으로 동작하는데 BFS는 반대다. BFS는 보통 큐 자료구조를 이용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 , 먼저 들어온것은 나가게 되어서, 가까운 노드부터 탐색을 진행하게 된다.

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 주에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3) 이걸 더 이상 할 수 없을떄까지 한다.

from collections import deque

def bfs(graph, start, visited): 
#graph는 인접 리스트로 표현한 것
#start는 시작점
#visited는 방문했는지 안했는지를 T/F로 표현
#큐 구현을 위해 deque 사용
	queue = deque([start])
    #지금 있는 곳의 노드는 방문처리
    visited[start] = True
    #queue가 빌떄까지 반복
    while queue:
    	v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
graph = [ []. [2,3,8], [1,7], [1,4,3]........]
visited = [False] * 9

bfs(graph, 1, visited)
    

#미로탈출 : NxM 크기의 직사각형 형태의 미로에 같혀있다. (1,1)에서 (N,M)까지 한 번에 한 칸씩 이동할 수 있다. 0,1로 되어있는데 1로만 가야하는데 가기위한 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산.

3 3
110
010
011 -> 5

제일 처음점을 (1,1)이라고 하면
(1,1),(1,2),(1,3)
(2,1),(2,2),(2,3)
(3,1),(3,2),(3,3) 이렇게 된다. 최소 경로할떄는 BFS로 푸는게 좋다. bfs는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 떄문이다.
저 예로 든다면
(1,1)을 방문처리를 해주고, (1,1)을 팝한다음에, 주변 노드중에서 방문하지 않은곳 (1,2)을 큐에 넣어주고 방문처리를 한다. 그러고 (2,2)을 팝하고 다시, 주변 노드에서 방문하지 않은 (3,2)로 간다. 또 거기서 동일하게 해서 (3,3)으로 간다. 그래서 5.

from collections 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]

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))