백준_2178 (미로 탐색 _ n*m 그래프 BFS)

• 링크 : https://www.acmicpc.net/problem/2178

---

이건 BFS네 -> 동빈나에서 같은 문제 있었음

다른점 : 테스트케이스가 다양함

• n x n 행렬이 아닌, n x m 행렬임을 주의한다!!!
• 그래서 "if ny < 0 or n <= ny or nx < 0 or m <= nx:" 부분을 graph의 length로 계산해서 지정해줘야 한다
• 그렇지 않으면 if문에 걸려서 n x n 만큼만 계산하고 queue에 다음 탐색할 노드를 안넣음(=중간에 끊김)

---

''' 내가 푼 - 하루 전에 동빈나 공부했던 거랑 똑같은 문제임 '''
from collections import deque

def bfs(s, graph, n, m):
   que = deque([s])
   #    상 하 좌 우
   dy = [-1, 1, 0, 0]
   dx = [0, 0, -1, 1]    
   
   # n * m 행렬이므로 (중요)
   n = len(graph)
   m = len(graph[0])
   
   while que:
       y, x = que.popleft()
       
       for i in range(4):
           ny = y + dy[i]
           nx = x + dx[i]
           
           if ny < 0 or n <= ny or nx < 0 or m <= nx:
               continue
           
           if graph[ny][nx] == 0:    # (중요) 이거 필수임
               continue
           
           if graph[ny][nx] == 1:
               graph[ny][nx] = graph[y][x] + 1
               que.append((ny, nx))
               # BFS는 재귀함수 없다!
                       
   return graph[n-1][m-1]          # 이 문제는 BFS 다 끝나고 N,M 위치에 값을 리턴한다

print(bfs((0,0),
         [[1,0,1,1,1,1],
         [1,0,1,0,1,0],
         [1,0,1,0,1,1],
         [1,1,1,0,1,1]], 4, 6))

print(bfs((0,0), 
         [[1,1,0,1,1,0],
         [1,1,0,1,1,0],
         [1,1,1,1,1,1],
         [1,1,1,1,0,1]], 4, 6))

print(bfs((0,0), 
         [[1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1], 
         [1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]], 2, 5))

print(bfs((0,0), 
         [[1, 0, 1, 1, 1, 1, 1], 
          [1, 1, 1, 0, 0, 0, 1], 
          [1, 0, 0, 0, 0, 0, 1], 
          [1, 0, 0, 0, 0, 0, 1], 
          [1, 0, 0, 0, 0, 0, 1], 
          [1, 0, 0, 0, 0, 0, 1], 
          [1, 1, 1, 1, 1, 1, 1]], 7, 7))

---

''' 내가 푼 - 백준용 '''
from collections import deque

def bfs(s, graph, n, m):
    que = deque([s])
    #    상 하 좌 우
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]    
        
    while que:
        y, x = que.popleft()
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if ny < 0 or n <= ny or nx < 0 or m <= nx:
                continue
            
            if graph[ny][nx] == 0:    # (중요) 이거 필수임
                continue
            
            if graph[ny][nx] == 1:
                graph[ny][nx] = graph[y][x] + 1
                que.append((ny, nx))
                # BFS는 재귀함수 없다!
                        
    return graph[n-1][m-1]          # 이 문제는 BFS 다 끝나고 N,M 위치에 값을 리턴한다

n, m = map(int, input().split())
graph = [list(map(int,input())) for _ in range(n)]

# n * m 행렬이므로 (중요)
new_n = len(graph)
new_m = len(graph[0])

print(bfs((0,0), graph, new_n, new_m))