[이코테] DFS/ BFS 실전문제 4 미로 탈출

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = int(1e9)
def bfs(graph,x,y):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    index = 2
    nx = 0
    ny = 0
    queue = deque()
    queue.append((x,y))

    while queue:
        flag = 0
        a,b = queue.popleft() # 큐에서 원소 2개를 빼오고
        graph[a][b] = -1 # 방문 처리해준다 
        for i in range(4):
           nx = a + dx[i] # x와 y의 방향 점검
           ny = b + dy[i]
           if nx < 0 or ny < 0 or nx >=N or ny >=M:
              continue # 인덱스 아웃 방지
           if graph[nx][ny] == 0 or graph[nx][ny] == -1:
              continue # 얘도 이미 방문한 애이므로 패스
           elif graph[nx][ny] == 1: # 횟수의 카운트
            flag = 1 # 셋중 하나라도 갱신이 발생했다는 뜻
            queue.append((nx,ny)) # 이웃한 노드의 번호를 모두 큐에 저장한다
            graph[nx][ny] = index # index라는 숫자로 모두 바꿔준다 (index의 회수에 거쳐 이 노드에 도달할 수 있다는 의미)
            if nx == N-1 and ny == M-1:
               break
        if nx == N-1 and ny == M-1:
               break
        if flag == 1: # 여기서 flag는 갱신이 한번이라도 일어난 것을 의미. 만약 주변을 둘러싼게 모두 0이고 혼자 1이라면 그것은 
               # 최단 경로로의 길이 아니므로 제외해야 한다
               index+=1    
    print(index)
    
N,M = map(int,sys.stdin.readline().split())
graph =[]

for i in range(N):
 graph.append(list(map(int,sys.stdin.readline().rstrip())))

bfs(graph,0,0)

참 어렵게 풀었죠......... 

제 풀이는 

방문한 노드는 0이랑 구분하기 위해서 -1로 바꾸어 주었고

만약

0 1 0

   0

이 경우에서 1이 최단거리중 하나의 길로 카운팅되는걸 방지하기 위해서

flag를 도입하였습니다

큐에서 뽑아온 원소에서 하나라도 갱신이 일어나면 index를 추가(최단경로에 포함)

아니더라면 인덱스 증가 X

테스트 케이스에서 걸리는 경우가 있었어요 이걸 해주지 않으면...

 

 

간단한 방법은 1이 나오면

graph[nx][ny] = graph[x][y] + 1 해주면 된답니다 ^^

비효율적인 풀이이지만 .. 혼자 고민하고 풀었다는 거에 의의를 두고 ,,,,

다음엔 효율적인 풀이로 찾아오겠습니다...

 

아래는 제가 문제 풀때 직접 확인하기 위해서 작성한 while문이 끝날때마다 그래프입니다 

-1 0 1 0 1 0 
2 1 1 1 1 1 
0 0 0 0 0 1 
1 1 1 1 1 1 
1 1 1 1 1 1 
deque([(1, 0)])

-1 0 1 0 1 0 
-1 3 1 1 1 1 
0 0 0 0 0 1 
1 1 1 1 1 1 
1 1 1 1 1 1 
deque([(1, 1)])

-1 0 1 0 1 0 
-1 -1 4 1 1 1 
0 0 0 0 0 1 
1 1 1 1 1 1 
1 1 1 1 1 1 
deque([(1, 2)])

-1 0 5 0 1 0 
-1 -1 -1 5 1 1 
0 0 0 0 0 1 
1 1 1 1 1 1 
1 1 1 1 1 1 
deque([(1, 3), (0, 2)])

-1 0 5 0 1 0 
-1 -1 -1 -1 6 1 
0 0 0 0 0 1 
1 1 1 1 1 1 
1 1 1 1 1 1 
deque([(0, 2), (1, 4)])

-1 0 -1 0 1 0 
-1 -1 -1 -1 6 1 
0 0 0 0 0 1 
1 1 1 1 1 1 
1 1 1 1 1 1 
deque([(1, 4)])

-1 0 -1 0 7 0 
-1 -1 -1 -1 -1 7 
0 0 0 0 0 1 
1 1 1 1 1 1 
1 1 1 1 1 1 
deque([(1, 5), (0, 4)])

-1 0 -1 0 7 0 
-1 -1 -1 -1 -1 -1 
0 0 0 0 0 8 
1 1 1 1 1 1 
1 1 1 1 1 1 
deque([(0, 4), (2, 5)])

-1 0 -1 0 -1 0 
-1 -1 -1 -1 -1 -1 
0 0 0 0 0 8 
1 1 1 1 1 1 
1 1 1 1 1 1 
deque([(2, 5)])

-1 0 -1 0 -1 0 
-1 -1 -1 -1 -1 -1 
0 0 0 0 0 -1 
1 1 1 1 1 9 
1 1 1 1 1 1 
deque([(3, 5)])