[DFS] -미로탈출

미로탈출

N x M 공간에 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다.

이 때 동빈은 (1,1) 즉, 왼쪽 상단에 있을 때 (N,M)즉, 오른쪽 최하단에 있는 미로로 최단 경로로 갈 때 시작 칸과 마지막 칸을 포함하여 총 몇칸을 지나는지 출력 하시오.

 

입력 예시)

5 6

101010

111111

000001

111111

111111

 

출력예시)

10

 

나의 코드

from collections import deque

def BFS(x,y,arr):
     print(n,m)
     dq=deque()
     dq.append([0,0])
     
     dx=[-1,0,1,0]
     dy=[0,1,0,-1]
     L=0
     while True:
        D=len(dq)
        for _ in range(D):
            x,y=dq.popleft()
            if x==n-1 and y ==m-1:
                return L+1
            for k in range(4):
                nx=x+dx[k]
                ny=y+dy[k]
                if 0<=nx<n and 0<=ny<m and arr[nx][ny]==1: 
                        arr[nx][ny]=0
                        dq.append([nx,ny])      
        L+=1
     

n,m=map(int,input().split())
arr=[list(map(int,input())) for _ in range(n)]
            
print(BFS(0,0,arr))

흠 생각 보다 시간이 오래 걸렸다.

아직 DFS보다 BFS의 이해도가 낮은것 같다.

처음 시작 점이 0인지 1인지에 대해 고민하다가 그림을 그려 입력값과 출력 값을 비교해서 출발점이 1이라는걸 확인했다.

아마 별다른 언급이 없으면 위와같이 좌표 평면 문제의 왼쪽상단을 (1,1)이라고 하는것 같군..!

+ 그리고 난 따로 시작점을 (1,1)로 두지 않고 (0,0)을 시작 점으로 입력값을 받고 최종 미로 지점의 좌표를 N-1,M-1로 함

 

 

그리고 BFS 함수를 따로 생성하지 않고 바로 while문으로 돌리다가 종료 지점에 출력값을 출력 한뒤 sys.exit()로 종료 할까 싶었는데 그건 뭔가(?) 꺼려져서 그냥 BFS를 함수로 생성했다.

그리고 큐에 더해질때마다 카운팅이 되는걸로 오해해서 디버깅을 꽤나 했다. 

깨달기전 어디서 문제가 생긴건지 확인하며 Print를 찍어 보다가 아 !@! 큐에 들어가는건 잘못된 경로도 포함이 되고 BFS의 레벨이 실직적으로 좌표상으로 이동한 거리가 되겠구나 ! 그리고 시작 레벨을 0으로 하였으니 최종 종료 레벨에 1을 더해서(문제 조건에 시작점도 카운팅을 하라고함 ) 반환 해야 겠구나 ! 라고 번뜩 떠올랐다.

 

 

 

아무튼 시간이 조금 소비 되었지만 많은 생각과 답을 끝까지 안보고 좋은 코드로 답을 도출해서 기분이가 조크든요 ㅋㅋ~

 

정답 코드

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))

이번 정답코드는 나쁘지 않은것 같다. 

나와 접근법도 비슷하다.(물론 contine를 써서 더 길어진건 거슬리는군..)

주요 기억할 핵심은 위 코드에서는 이동한 거리는 입력된 공간에 1씩 더해서 체크 리스트 역활을 한 동시에 이동한 거리를 저장하게 하였다.

위 방법은 기억을 해야겠다 !!