[SWEA] [파이썬 S/W 문제해결 기본] 6일차 - 미로의 거리 (python)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

🔥 작성 코드

def bfs(si, sj, N):
    # 초기 데이터 설정
    q = []
    v = [[-1]*N for _ in range(N)]
    q.append([si, sj])
    v[si][sj] = 0

    while q:
        si, sj = q.pop(0)
        # 4방향 탐색
        for di, dj in ((1, 0), (-1, 0), (0, -1), (0, 1)):
            ni, nj = si+di, sj+dj

            # 갈 수 있다면 q에 삽입, 방문 배열에 이전 값 +1
            if 0 <= ni < N and 0 <= nj < N and v[ni][nj] == -1 and arr[ni][nj] != '1':

                # 도착점을 찾으면 이전까지 온 칸 수 리턴
                if arr[ni][nj] == '3':
                    return v[ni-di][nj-dj]
                q.append([ni, nj])
                v[ni][nj] = v[si][sj] + 1
    # 못 찾았다면 0
    return 0

T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    arr = [input() for _ in range(N)]

    # 시작 위치 탐색
    for i in range(N):
        for j in range(N):
            if arr[i][j] == '2':
                si, sj = i, j
    result = bfs(si, sj, N)
    print(f'#{test_case} {result}')

 

⭕ 해설

1.  q를 활용하여 너비우선탐색(BFS)
2.  v 를 -1로 초기화 시키고 시작점에 0을 넣어줍니다.
3.  방문 배열 v에 출발지에서부터 이동한 칸 수를 저장하며 이동합니다.
4.  도착지를 찾으면 이 전 칸의 v에 저장된 값을 return합니다.

 

🚨 이 전 미로문제에서는 dfs를 이용하였지만 보통 이런 문제는 bfs를 사용합니다.

 

 

---

미로 문제(DFS)

 

 

2022.02.24 - [Algorithm/SWEA] - [SWEA] [파이썬 S/W 문제해결 기본] 5일차 - 미로 (python)

[SWEA] [파이썬 S/W 문제해결 기본] 5일차 - 미로 (python)