[백준] 2178 - 미로 탐색 (파이썬, Python)

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

처음 문제를 접했을 때 어떻게 접근해야 할지 막막했다.

그러다 문득 아래와 같은 생각이 들었다.

 

#현재까지 지나온 칸의 수 = 전 칸의 지나온 칸의 수 + 1

 

실마리를 찾은 것 같아서 기뻤다.

바로 적용해 보았다.

from collections import deque
import sys

def solution():
    visited = []
    queue = deque([(0,0)])
    step_matrix[0][0] = 1
    while queue:
        cur_row, cur_col = queue.popleft()
        cur_step = step_matrix[cur_row][cur_col]
        if (cur_row, cur_col) not in visited:
            visited.append((cur_row, cur_col))
            tmp = []
            if(cur_row > 0 and adj_matrix[cur_row -1][cur_col] == 1 and cur_step < step_matrix[cur_row-1][cur_col]):
                tmp.append((cur_row-1, cur_col))
                step_matrix[cur_row-1][cur_col] = cur_step + 1
                
            if(cur_col > 0 and adj_matrix[cur_row][cur_col -1] == 1 and cur_step < step_matrix[cur_row][cur_col-1]):
                tmp.append((cur_row, cur_col-1))
                step_matrix[cur_row][cur_col-1] = cur_step + 1

            if(cur_col < M-1 and adj_matrix[cur_row][cur_col +1] == 1 and cur_step < step_matrix[cur_row][cur_col+1]):
                tmp.append((cur_row, cur_col+1))
                step_matrix[cur_row][cur_col+1] = cur_step + 1
            if(cur_row < N-1 and adj_matrix[cur_row +1][cur_col] == 1 and cur_step < step_matrix[cur_row+1][cur_col]):
                tmp.append((cur_row+1, cur_col))
                step_matrix[cur_row+1][cur_col] = cur_step + 1

            queue.extend(tmp)
    
    return step_matrix[N-1][M-1]

my_input = lambda : sys.stdin.readline().rstrip()

N, M = map(int, my_input() .split())

adj_matrix = [[int(j) for j in my_input()] for i in range(N)]

step_matrix = [[999999 for j in range(M)] for i in range(N)]

print(solution())

 

 

 

성공했다.

그러나 코드가 너무 지저분하고 실행 시간이 오래 걸렸다.

스스로 부족함을 또 한 번 깨닫고 다른 분들의 코드를 참고하기로 했다.

 

---

from collections import deque
import sys

def solution():
    mx = [-1, 0, 1, 0]
    my = [0, 1, 0, -1]
    visited[0][0] = 1
    queue = deque([(0,0)])

    while queue:
        cur_x, cur_y = queue.popleft()
        for i in range(4):
            new_x = cur_x + mx[i]
            new_y = cur_y + my[i]
            if(new_x >= 0 and new_x < N and new_y >= 0 and new_y < M):
                if(visited[new_x][new_y] == 0 and adj_matrix[new_x][new_y] == 1):
                    queue.append((new_x, new_y))
                    visited[new_x][new_y] = visited[cur_x][cur_y] +1

    return visited[N-1][M-1]

my_input = lambda : sys.stdin.readline().rstrip()

N, M = map(int, my_input() .split())

adj_matrix = [[int(j) for j in my_input()] for i in range(N)]

visited = [[0]*M for i in range(N)]

print(solution())

 개선 사항

1. 조건문 수를 줄였다.

#개선 전
if(cur_row > 0 and ...) :
	...
if(cur_row < M -1 ...) :
	...
if(cur_col > 0 ...) :
	...
if(cur_col < N -1 ...) :
	...
=> 위와 같이 이동 가능한 칸의 판별을 위해 4개의 if문 사용

#개선 후
if(new_x >= 0 and new_x < N and new_y >= 0 and new_y < M):
	if(visited[new_x][new_y] == 0 and adj_matrix[new_x][new_y] == 1):
=> 위와 같이 조건문을 중첩하여 판별

2. 방문 여부를 이용하여 지나온 타일 수를 계산했다.

 

#bfs를 이용하므로 이미 방문한 기록이 있는 칸의 step 수(지나온 칸의 수)는 현재 step 수보다 작다.
#따라서 방문 기록이 없는 칸에 step 수를 업데이트 하면 그 값이 해당 칸의 최소 step 수이다.

 

 

항상 코드를 참고할 때 많은 사람들의 코드를 보고 공통된 형식이 있는지 확인한다.

이 문제도 역시 공통된 형식이 있었다.

하나 더 배워가는 문제였다.

 

---

참고 코드

https://j-remind.tistory.com/52