[SW Expert Academy] 5105번 미로의 거리 python

문제의 저작권은 SW Expert Academy에 있습니다.

5105. 미로의 거리

문제

NxN 크기의 미로에서 출발지 목적지가 주어진다. 이때 최소 몇 개의 칸을 지나면 출발지에서 도착지에 다다를 수 있는지 알아내는 프로그램을 작성하시오.

풀이

bfs을 통해 이차원의 최소 거리 찾기
경로같은 경우는 dfs를 써야한다.
bfs는 모든칸의 경우를 최단 거리로 탐색하기 때문이다.
출발지와 목적지가 주어짐.
벽으로 둘러쌓인 경우가 아니기 때문에 범위 안넘어가게 고려를 해야한다.
경로 있으면 지나가는 칸수를 세면 되고 없으면 0을 출력하면된다.

5
13101
10101
10101
10101
10021

입력값을 문자열로 '13101'이런식으로 넣어도 되고 아니면 리스트로 [1, 3, 1, 0, 1]로 리스트로 2차 배열 을 해도된다.

dfs로 모든 길이 다 탐색해서 길이가 가장 짧은거 해도 가능은 하지만, BFS가 더 간단하다.

---

BFS의 슈도코드

BFS(G,V)  # g는 그래프, 탐색 시작점 v
    큐생성
    시작점 v를 큐에 삽입
    점 v를 방문한 것으로 표시

while 전에 큐에 시작점을 넣고
여기서 시작점은 튜플 안에 (y, x)로 넣는다.
visited에 1을 체크한다.

while que: #que가 비어있지 않은 경우만 탐색한다

while 문을 돌릴려면 que에 하나를 넣고 시작해야한다.

while 들어가자마자 que.popleft()로 큐를 뺀 후에 변수에 넣는다.
문제에 맞는 조건을 넣는다.
변수 가 목적지인 경우 visited[t]를 리턴.

그리고 for문을 통해 인접점들확인을 한다.
조건에 만족하면 que.append(x)를 통해 인큐를 하고 방문 표시를 한다.

출력전에 우리가 계산 한 값과 출력값이 -2차이가 나기 때문에 -2를 하고 출력을 해준다.

코드

def bfs(y, x):
    q = (y, x)
    visited = [[0]*(N+1) for _ in range(N+1)]
    deq = collections.deque()
    deq.append(q)
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[y][x] = 1
    while deq:
        i, j = deq.popleft()
        if data[i][j] == 3:
            return visited[i][j]
        for k in range(4):
            nx = dx[k] + j
            ny = dy[k] + i
            if not(0 <= nx < N and 0 <= ny < N):
                continue
            if (data[ny][nx] == 0 or data[ny][nx] == 3) and visited[ny][nx] == 0:
                deq.append((ny, nx))
                visited[ny][nx] = visited[i][j] + 1
    return 2


import collections
import sys
sys.stdin=open("5105미로의거리.txt")

TC = int(input())
for tc in range(1, TC+1):
    N =int(input())
    data = [list(map(int, input())) for _ in range(N)]
    c=2
    for i in range(N):
        for j in range(N):
            if data[j][i] == 2:
                c = bfs(j, i)
    print("#%d %d"%(tc, c-2))