[백준/python][stack] 24463번 - 미로

 

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

24463번: 미로

입력

첫 번째 줄에는 미로의 크기 N, M이 주어진다. (3≤N, M≤2,001, N, M은 홀수)

두 번째 줄부터는 미로의 정보가 주어진다. 두 번째 줄부터 N줄에 거쳐 각 줄에는 길이가 M이고 .과 +만으로 이루어진 문자열이 주어진다.

같은 지점으로 돌아오는 길이 존재하지 않고, 두 구멍 사이를 이동할 수 있는 미로만 주어진다.

---

출력

주어진 미로를 최단 거리로 이동하는 데 사용하지 않은 길을 @로 표시한 결과를 출력한다.

---

코드

import sys 

def miro_chk():
    global miro 
    global stack, path, delete 

    temp_cnt = 0
    s_x = start[0]
    s_y = start[1]
    path.append([s_x, s_y])
    miro[s_x][s_y] = '@'
    
    while True:
        if s_x==end[0] and s_y==end[1]: # 목적지에 도착했다면
            break
    
        cnt = 1
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: # 점이 상하좌우
            nx, ny = s_x+dx, s_y+dy
            if 0<=nx<h and 0<=ny<w and miro[nx][ny] == '.':
                stack.append([nx, ny, cnt]) 
                temp_cnt += 1  
            cnt += 1  
        
        if temp_cnt == 0: # 이번에 갈곳이 없다면
            if stack[-1][2] == 1:
                x = 1
                y = 0
            elif stack[-1][2] == 2:
                x = -1
                y = 0
            elif stack[-1][2] == 3:
                x = 0
                y = 1
            else:
                x = 0
                y = -1
            x = stack[-1][0] + x
            y = stack[-1][1] + y
        
            for i in range(len(path)-1, -1, -1):
                temp = str(abs(path[i][0]-x)) + str(abs(path[i][1]-y))
                if temp=="01" or temp=="10":
                    del path[i:]   
                    break
            
        temp_cnt = 0 # 초기화 
        if stack: # stack이 비지 않았다면 
            miro[s_x][s_y] = '@' # !대입 지나온 길임
            path.append(stack[-1][0:2])
            s_x = stack[-1][0]
            s_y = stack[-1][1]
            stack.pop()
        else:
            break

r_line = sys.stdin.readline
h, w = map(int, r_line().split())

miro = [[] for _ in range(h)]
stack = []
path = []
se = []
delete = []
for i in range(h):
    miro[i] = list(r_line().rstrip())

for i in range(h): # 행만큼 반복
    if miro[i][0] == '.':
        se.append([i, 0])        
    if miro[i][w-1] == '.': 
        se.append([i, w-1])

for i in range(w): # 열만큼 반복
    if miro[0][i] == '.':
        se.append([0, i])        
    if miro[h-1][i] == '.': 
        se.append([h-1, i])

    
start = se[0]
end = se[1] 

 miro_chk()

for i in range(h): # 행만큼 반복
    for j in range(w): # 열만큼 반복
        if miro[i][j] == '.':
           miro[i][j] = '@' 
           
for i in path:
    miro[i[0]][i[1]] = '.'

for i in range(h):
    print(''.join(miro[i]))

---

풀이

풀이 순서는 다음과 같다.

1. 시작점, 끝 점 조사

2. 현재좌표를 기준으로 갈 수 있는 지점 조사 

3. 조사를 통해 전진 or 갈 곳이 없다면 스택에 저장된 갈림길지점으로 회귀하며 막힌길 제거

4. path리스트에 기록된 탈출루트를 통해 '.', '@'을 매핑 

 

 

스택을 이용하여 미로찾기문제를 해결하는방법으로 아이디어를 얻어서 풀었다.

여기서 문제에서 함정은 최단거리이다.

문제를 분석하는 시간을 오래잡은거 같은데, 분석을 한 결과, 최단거리는 없다. 왜냐하면

"같은 지점으로 돌아오는 길이 존재하지 않고, 두 구멍 사이를 이동할 수 있는 미로만 주어진다."

이런 문구를 해석하면 길은 오직하나이기 때문이다.

따라서 최단거리와 상관없이 길은 오직 1개이며, 막힌길만이 존재 할 뿐이다.

 

1. 가(가장자리)에 시작점, 끝 점이 존재한다고 하였기에 시작점, 끝점을 조사한다.

for i in range(h): # 행만큼 반복
    if miro[i][0] == '.':
        se.append([i, 0])        
    if miro[i][w-1] == '.': 
        se.append([i, w-1])

for i in range(w): # 열만큼 반복
    if miro[0][i] == '.':
        se.append([0, i])        
    if miro[h-1][i] == '.': 
        se.append([h-1, i])

시작점, 끝점을 조사하는 코드는 다음과 같다.

가장자리 == 양끝만을 의미하는게 아니고, 상하 까지 합쳐서 모서리 전부를 뜻한다.

(이를 잘 못 이해해 문제의 많은 시간을 쏟았다.)

 

2. 현재좌표를 기준으로 조사

   cnt = 1
        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]: # 점이 상하좌우
            nx, ny = s_x+dx, s_y+dy
            if 0<=nx<h and 0<=ny<w and miro[nx][ny] == '.':
                stack.append([nx, ny, cnt]) 
                temp_cnt += 1  
            cnt += 1

상하좌우로 더해가며, 끝점을 가지않도록 if문을 설계하고 갈 수 있는 갈림길들을 차례로 

stack에 저장한다.

 

3. 조사를 통해 전진 or 갈 곳이 없다면 스택에 저장된 갈림길지점으로 회귀하며 막힌길 제거

   if temp_cnt == 0: # 이번에 갈곳이 없다면
            if stack[-1][2] == 1:
                x = 1
                y = 0
            elif stack[-1][2] == 2:
                x = -1
                y = 0
            elif stack[-1][2] == 3:
                x = 0
                y = 1
            else:
                x = 0
                y = -1
            x = stack[-1][0] + x
            y = stack[-1][1] + y
        
            for i in range(len(path)-1, -1, -1):
                temp = str(abs(path[i][0]-x)) + str(abs(path[i][1]-y))
                if temp=="01" or temp=="10":
                    del path[i:]   
                    break

만약에 이번에 갈 곳이 없게 된다면 여기 if문에 걸리게 된다.

if문에 걸리면 갈림길로 점프하게 되고, 이전에 잘 못해서 온 길은 다시 path(경로)에서 삭제해야 한다. 

따라서 갈림길 좌표를 얻고 그에따라 새롭게 이동할려는 좌표까지를 stack에서 꺼내서, 내가 지워야하는 곳까지 for문으로 돌려서 찾고 찾았다면 path에서 경로를 지운다. (이 문제는 여기가 핵심 알고리즘이다.)

 

마지막 path에 저장된 경로를 통해 2차원행렬을 매핑해주고 출력한다.