실1
bfs 문제이다.
특정 목적지로 가는데 최소거리를 구하라고 하는 문제는 bfs 문제일 확률이 높다.
bfs의 경우 시작점에서부터 갈 수 있는 모든 목적지를 breadth(너비) 기준으로 탐색하기 때문에, 처음으로 목적지를 만나는 시점이 최소거리로 그 목적지를 갈 수 있는 거리이다.
-
가장 먼저 생각해야 될 부분은 x, y를 기준으로 움직이는 코드를 짜는 것이다.
1-1. 입력으로 받은 배열을 올바르게 처리해서 2차원 배열로 만들어 주어야 한다.
1-2. 시작점으로 부터 x -> 오른쪽, 왼쪽, y -> 위, 아래를 움직이는 코드를 만든다. -
bfs 는 queue와 궁합이 좋다. 파이썬의 deque 라이브러리를 통해 queue를 만들고 while 문을 돌며 queue에 방문할 노드들을 순서대로 집어넣어준다.
-
마지막으로 visited 한 노드들을 방문 처리 해주어야 한다. 이 부분을 제대로 처리해주지 않으면 시간초과 or 메모리 초과가 발생한다.
시간초과의 경우 방문 노드를 제대로 처리해주지 못해서 방문한곳을 계속 재방문 하게 되어, 시간이 많이 발생하게 되고, 메모리 초과 또한 재방문한 노드를 계속 queue에 삽입하게 되어 메모리가 늘어서 메모리 초과가 발생하게 된다.
혹시 visited 배열을 이용해서 방문 노드를 처리하면 시간 초과가 발생한다. 기본적으로 visited는 리스트기 때문에, 특정 원소를 찾으려면 O(n)의 시간이 소요된다. 해당 노드가 방문되었는지 안되었는지, 이동할 때마다 확인하면 이 부분에서 시간이 너무 많이 걸려 시간초과가 발생할 수 있다.
이 경우에는 visited 배열을 이용하는 것이 아니라, 방문한 그래프의 노드 값을 0으로 바꿔주어야 한다.
from collections import deque
n, m = map(int, input().split(" "))
arr = [list(map(int, list(input()))) for _ in range(n)]
count = 0
def solution():
global count
dq = deque([[[0, 0], 1]]) # dq에 노드와 해당 노드를 도착했을 때의 이동한 카운트 거리를 함께 저장
while dq:
temp, count = dq.popleft()
if temp == [m - 1, n - 1]: # 목적지 도착시 while 문 탈출
print(count)
break
right = temp[0]+1 # 중복계산 회피를 위한 코드
left = temp[0]-1
up = temp[1]-1
down = temp[1]+1
if right < m: # 배열을 벗어나 index error를 막기 위함
if arr[temp[1]][right] == 1: # 내가 갈 곳이 1이라면 dq에 넣어줌
dq.append([[right, temp[1]], count + 1]) # 다음 번에 방문할 노드 저장
arr[temp[1]][right] = 0 # 방문 노드 0으로 변경
if down < n:
if arr[down][temp[0]] == 1:
dq.append([[temp[0], down], count + 1])
arr[down][temp[0]] = 0
if left >= 0:
if arr[temp[1]][left] == 1:
dq.append([[left, temp[1]], count + 1])
arr[temp[1]][left] = 0
if up >= 0:
if arr[up][temp[0]] == 1:
dq.append([[temp[0], up], count + 1])
arr[up][temp[0]] = 0
solution()
