[Algorithm] (이코테) 미로 탈출 - 파이썬

교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 5 DFS/BFS
실전문제 5-4 미로 탈출 152p

미로 탈출

문제

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력

첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6
101010
111111
000001
111111
111111

출력 예시

10

풀이

접근 1

1. 방향저장해서 확인하기
2. 처음에 재귀하는 형식으로 풀려다가 정신차리고 queue 개념 끌고와서 풀 방법 고민했다
3. 큐에서 하나 pop할때마다 cnt 더해주고 일단 만나는거 다 큐에다가 박아주는데 4방향에서 append하는게 하나라도 없으면 cnt 하나 다시 빼주는 형식으로 구현

Note

0. 위치 옮겨갈때 자리마다 숫자 올려주는 개념 솔직히 생각못했었음 ㅠㅠ 하.. 멀고도 험한 알고리즘 세상
1. 동쪽부터 저장했더니 엉켜서 북쪽부터 시계방향으로 저장함 ㅜ(이딴식으로 풀어도 괜찮은걸까;;)
2. 헤멤 포인트는 visited = board를 복사개념이라고 생각하고 board를 다른데다가 쓰려고 했는데 이게 약간 주소? 까지 같아지는 그런거였다..
   진짜 파이썬 ㄹㅇ 알다가도 모르겠음 그래서 여기서 좀 시간 허비한듯 ㅠㅠ

제출 1 - 정답

from collections import deque

n,m = map(int,input().split())
board =[]
dx = [0,1,0,-1]
dy = [-1,0,+1,0]

for i in range(n):
    board.append(list(map(int,input())))
visited = board
def bfs(y,x):
    cnt = 1
    global visited, board
    visited[y][x]= 0
    q = deque()
    q.append((y,x))

    while 1:
        (y,x) = q.popleft()
        cnt+=1
        count=0
        for j in range(4):
            tx = x + dx[j]
            ty = y + dy[j]
            if tx>=0 and tx<m and ty>=0 and ty<n and visited[ty][tx]==1:
                if ty == n-1 and tx == m-1:
                    return cnt
                visited[ty][tx] = 0
                q.append((ty,tx))
                count+=1
        if count==0:
            cnt-=1
                
print(bfs(0,0))

오답노트

풀이에서는 해당 노드를 처음 방문할 때 내 위치의 거리에다가 1을 더해서 저장하는 식으로 구현을 했다.. 사실 이 외 부분은 비슷하긴 한데 cnt 더했다 빼는게 계속 꺼림찍해서 다른 방법으로 구현하고 싶고 그랬는데 솔루션 보자마자 묵힌 한?이 싹 내려가는 기분을 느꼈다 ㅋㅋㅋ 집중해서 풀지는 못해서 dfs랑 bfs 시간을 못쟀는데 뭔가 둘다 좀 풀면서 학습해야하는 내용이 많았어서 이게 나았던 것 같다 괜히 뭔가 어거지로 풀라고 했으면 진짜 개판으로 풀었을듯..ㅋㅋ dfs는 좀 비효율적으로 푼 것 같아서 아쉽지만 bfs는 좀 덜해서.. 괜히 뿌듯했다ㅋㅋ 앞으로 다른 연습문제 진자 많이 풀어봐야할 것 같당

• 책에 있는 솔루션

from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x, y))
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 찾기 공간을 벗어난 경우 무시
            if nx < 0 or nx >= n or ny < 0 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]

# BFS를 수행한 결과 출력
print(bfs(0, 0))

결과

• 풀이시간 : 60분/30분 (Omg.. 다시풀자..다시풀자...다시풀어...)

References

이것이 코딩 테스트다 with 파이썬 - 나동빈 저