Bucket Brigade – 실버 4

BFS: 함수의 return 조건은 찾고자 하는 값을 찾았을 때이며 queue를 사용하여 모든 범위를 확인할 수 있기에 최단거리만이 아니라 넓이와 같은 문제에서도 사용할 수 있다.

 

1. Queue를 이용한다.

2. d=[(-1,0),(1,0),(0,-1),(0,1)]를 선언 해당 d를 반복문으로 더 했을 때 행렬의 범위를 벗어나는지 확인.

3. 해당 조건을 완수 혹은 탐색 값인 경우의 조건문 확인 후, 조건 완료 시 return, 탐색 값일 경우 전 값에 초기화 +1을 하여 거리를 작성해두자.

 

* 외워야 할 포인트

    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q: # bfs에서는 queue를 사용하여 반복문을 이용해서 탐색을 한다.
        y, x = q.popleft()
        for dy, dx in d: # map 안의 xy를 모두 반복해서 탐색.
            Y, X = y+dy, x+dx

정답 코드

from collections import deque
def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q: # bfs에서는 queue를 사용하여 반복문을 이용해서 탐색을 한다.
        y, x = q.popleft()
        for dy, dx in d: # map 안의 xy를 모두 반복해서 탐색.
            Y, X = y+dy, x+dx
            if (0 <= Y < 10) and (0 <= X < 10):
                if graph[Y][X] == 'L':
                    return graph[y][x]
                if graph[Y][X] == '.':
                    q.append((Y, X))
                    graph[Y][X] = graph[y][x]+1 # 전의 값에 1을 더해서 cnt 값을 출력하기 위함.

graph = [list(input()) for _ in range(10)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(10):
    for j in range(10):
        if graph[i][j] == 'B':
            cnt = bfs(i, j)
print(cnt)