[PYTHON] 백준 2178 - 미로 탐색

성능 요약

메모리: 116456 KB, 시간: 200 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

---

아이디어, 문제풀이

• dfs의 포문은 다리를 체크하기 위한 포문이라고 생각해야한다.

---

TROUBLE SHOOTING

• 일단 첫 bfs 문제풀이 였는데, 역시나 기억이 안났다. 이 문제를 풀이하면서 총 4개의 코드를 작성했는데, 첫문제에서 확실히 이해하고 넘어가고 싶어서 거의 1시간을 파고들었다. 가장 기본적인 문제여서, bfs함수를 이해하고, 자유롭게 조작할수 있을만큼 수정하고 건드려 봤다. 아래 내용들은 그런 과정속에서 알아낸것들이 대부분이다. 역시 어려울줄 알았다. 파이팅..

• 일단, 다른 코드상에서는 입력값을 strip() 없이 받아오는걸 봤다.

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

  만약 나처럼,

  import sys
  input = sys.stdin.readline이

  이 기능을 사용하는 사람이라면, strip()없이 구현할 수 없다. 그 이유는! 계속해서 대기상태가 되기 때문 /n 에 걸려 입력이 마무리 되지 않는다.
  

• 아래는 내가 처음 bfs 함수를 만들때 넣었던 매개변수들인데, 이번기회를통해 확실히 알았다.

  def bfs(graph, start, visit, cnt):
  일단 다 넣고 쓸모없는거 빼면된다!
  

• 아래는 상하좌우로 움직인다는 개념을 코드로 구현한것이다.

  dx = [1, -1, 0, 0]  # 오른쪽 왼쪽
  dy = [0, 0, 1, -1]  # 아래 위
  
  ---
  
  for i in range(4):
              nx = x + dx[i]
              ny = y + dy[i]

  앞으로도 자주 쓸 개념이니 놓치지 않고 이해할 수 있기를!..
  

• 리스트와 튜플의 차이

  que.append([x,y]) #?
  
  que.append((x,y)) #?

  튜플은 수정이 불가능하고, 리스트 형식은 수정이 가능하다는 장점이 있지만, 그때문에 리스트형식의 코딩이 좀더 많은 메모리를 사용하게 된다. 아래는 chat gpt의 답변이다.

  두 코드 사이의 차이는 리스트([])와 튜플(())의 사용입니다.

  que.append([x, y]): 여기서는 x와 y를 리스트 [x, y]로 만들어 que에 추가합니다. 리스트는 수정이 가능한(mutable) 자료구조입니다. 즉, 나중에 필요에 따라 리스트의 요소를 변경할 수 있습니다.

  que.append((x, y)): 여기서는 x와 y를 튜플 (x, y)로 만들어 que에 추가합니다. 튜플은 수정이 불가능한(immutable) 자료구조입니다. 즉, 튜플이 한 번 생성되면 요소를 변경할 수 없습니다.

  이 문제에서는 리스트와 튜플 중 어떤 것을 사용하더라도 코드가 정상적으로 작동합니다. 그러나 일반적으로는 튜플을 사용할 때 성능이 약간 더 좋습니다. 이는 튜플이 수정 불가능하므로 파이썬 인터프리터가 메모리를 더 효율적으로 관리할 수 있기 때문입니다. 여기서는 큰 차이가 없지만, 큰 데이터셋에서 작업할 때는 성능 차이가 나타날 수 있습니다.
  

---

코드

#https://www.acmicpc.net/problem/2178
#미로 탐색
#2178

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

graph = []

for i in range(n):
    a = list(map(int, input().strip()))
    graph.append(a)

# print(graph)

dx = [1, -1, 0, 0]  # 오른쪽 왼쪽
dy = [0, 0, 1, -1]  # 아래 위

# visit = [[0] * m for _ in range(n)]

# print(visit)

# print(cnt)

def bfs(x,y):

    que = deque()
    que.append([x,y]) #?

    while que:
        x, y = que.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #i=1 / 오른쪽
            #i=2 / 왼쪽
            #i=3 / 아래
            #i=4 / 위

            #행렬 외부로 가는곳은 전부다 안됨
            if nx<0 or nx>= n or ny<0 or ny>=m:
                continue
            
            #0인곳은 안됨
            if graph[nx][ny] == 0:
                continue

            if graph[nx][ny] == 1:
                #cnt를 따로 설정 안하고, 그 그래프에데가 이전 그래프의 값을 넣어주는거임
                graph[nx][ny] = graph[x][y] + 1
                que.append([nx,ny])

    return graph[n-1][m-1]

print(bfs(0,0))