NxN 크기의 미로에서 출발지 목적지가 주어진다.
이때 최소 몇 개의 칸을 지나면 출발지에서 도착지에 다다를 수 있는지 알아내는 프로그램을 작성하시오.
경로가 있는 경우 출발에서 도착까지 가는데 지나야 하는 최소한의 칸 수를, 경로가 없는 경우 0을 출력한다.
다음은 5x5 미로의 예이다. 1은 벽, 0은 통로를 나타내며 미로 밖으로 벗어나서는 안된다.
13101
10101
10101
10101
10021
마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 5개의 칸을 지나 도착할 수 있다.
[입력]
첫 줄에 테스트 케이스 개수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 미로의 크기 N과 N개의 줄에 걸쳐 미로의 통로와 벽에 대한 정보가 주어진다. 5<=N<=100
0은 통로, 1은 벽, 2는 출발, 3은 도착이다.
[출력]
각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.
이것은 바로바로 말로만 듣던 BFS 문제인 것인가.
사실 bfs 코드 보고 영차영차 따라해봤다.
dfs랑 코드로 봤을 때 차이도 아직 잘 모르겠다.
백 문제 풀어보면 알겠쥐?
# 상하좌우 방향을 살펴서 0이 있나 없나 깨알같이 확인할텨
dr = [0, -1, 0, 1]
dc = [-1, 0, 1, 0]
def bfs(start_row, start_col):
# 큐 생성하고 바로 첫 번째 요소 집어 넣기
q = [(start_row, start_col)]
# 그리고 바로 방문 췍
visited[start_row][start_col] = 1
while q:
# 첫 번째 요소 pop 은 국룰이 아니요
row, col = q.pop(0)
# 이 while문의 종료 조건은 3인 아이를 찾았을 때
if arr[row][col] == 3:
# 2를 뺀 이유는 시작과 도착때도 visited에 1씩 추가가 되었기 때문에
return visited[row][col] - 2
# 상하좌우 방향에 있는 애기들을 살필 것이여
for i in range(4):
nr = row + dr[i]
nc = col + dc[i]
# 혹시 nr, nc가 숫자가 인덱스 수를 넘어간다면 위로 올라가 아니라면 통과~
if nr < 0 or nr >= N or nc < 0 or nc >= N: continue
# 상하좌우 애기들의 번호가 0이거나 3이고 방문도 하지 않았다면 월척이요
if (arr[nr][nc] == 0 or arr[nr][nc] == 3) and visited[nr][nc] == 0:
# 큐에다가 갓 찾은 아이를 푸쉬
q.append((nr, nc))
# 방문 췤도 하는데 앞의 방문췍 한 아이보다 1을 추가해야 함. 왜냐하면 이것은 최단 거리 찾는 것이니까
visited[nr][nc] = visited[row][col] + 1
# 값이 없다면야 0을 리턴
return 0
for tc in range(1, int(input())+1):
N = int(input())
arr = [list(map(int, input())) for _ in range(N)]
visited = [[0] * N for _ in range(N)]
# 시작점을 찾아보아요
for i in range(N):
for j in range(N):
if arr[i][j] == 2:
start_row = i
start_col = j
print('#{} {}'.format(tc, bfs(start_row, start_col)))호호,, 오늘 처음으로 3문제를 푸는 영광을,,,
갹