[파이썬] 백준 17090 : 미로 탈출하기 (골드3)

[파이썬] 백준 17090 : 미로 탈출하기 (골드3)

 

 

17090번: 미로 탈출하기

---

문제

 

---

풀이

0. 방향성 생각

DP 태그 있어서 이용할 수도 있는데 내리막길 문제처럼 경로의 수를 카운트 하는게 아니라서 안써도 무방하다.

1. padding : 외곽 'x'로 채우기
2. 탈출 가능한 외곽지점 큐에 추가
3. 탈출 가능 지점에서 BFS 진행.
오른쪽 탐색 -> L이면 탈출 가능
왼쪽 탐색 -> R이면 탈출 가능
위쪽 탐색 -> D면 탈출 가능
아래쪽 탐색 -> U면 탈출 가능
4. 남은 'x'가 아닌 문자 카운트 : 탈출 불가
5. h*w - 탈출불가 개수

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = []
for i in range(h+2):
    if i==0 or i==h+1:
        arr.append(['x']*(w+2))
    else:
        temp = list(input())
        temp = ['x'] + temp + ['x']
        arr.append(temp)

외곽 padding 해주기

 

2. 탈출 가능한 외곽지점 탐색

q = deque()
for i in (1,h):
    for j in range(1,w+1):
        if i==1 and arr[i-1][j] == 'x' and arr[i][j] == 'U':
            q.append((j,i))
        if i==h and arr[i+1][j] == 'x' and arr[i][j] == 'D':
            q.append((j,i))
            
for i in range(1,h+1):
    for j in (1,w):
        if j==1 and arr[i][j-1] == 'x' and arr[i][j] == 'L':
            q.append((j,i))
        if j==w and arr[i][j+1] == 'x' and arr[i][j] == 'R':
            q.append((j,i))

외곽에서만 탐색해서 탈출 가능 유무를 확인하고 가능하면 큐에 추가한다.

 

3. BFS 진행

step = [[1,-1,0,0],[0,0,1,-1]]
while q:
    x,y = q.popleft()
    arr[y][x] = 'x'
    for i in range(4):
        nx = x + step[0][i]
        ny = y + step[1][i]

        if 0<=nx<=w+1 and 0<=ny<=h+1:
            if i==0 and arr[ny][nx] == 'L' :
                q.append((nx,ny))
            if i==1 and arr[ny][nx] == 'R' :
                q.append((nx,ny))
            if i==2 and arr[ny][nx] == 'U' :
                q.append((nx,ny))
            if i==3 and arr[ny][nx] == 'D' :
                q.append((nx,ny))

탈출 가능지점에서 오른쪽으로 갔는데 그 지점이 L이면 탈출가능 지점으로 올 수 있다.

탈출 가능지점을 'x'로 바꿔주면서 탐색하면 탐색이 끝난 후에 탈출 가능 지점들은 모두 'x'로 바뀐다.

 

동작 과정

테스트 케이스2의 탐색 과정을 나타내면 다음과 같다

다음좌표, 다음 좌표값, i (오른쪽 왼쪽 아래 위 순서이다.)

['x', 'x', 'x', 'x', 'x']
['x', 'D', 'D', 'R', 'x']
['x', 'D', 'L', 'U', 'x']
['x', 'L', 'L', 'L', 'x']
['x', 'x', 'x', 'x', 'x']
deque([(3, 1), (1, 3)])
(4, 1) x 0
(2, 1) D 1
(3, 2) U 2
(3, 0) x 3
['x', 'x', 'x', 'x', 'x']
['x', 'D', 'D', 'x', 'x']
['x', 'D', 'L', 'U', 'x']
['x', 'L', 'L', 'L', 'x']
['x', 'x', 'x', 'x', 'x']
deque([(1, 3), (3, 2)])
(2, 3) L 0
(0, 3) x 1
(1, 4) x 2
(1, 2) D 3
['x', 'x', 'x', 'x', 'x']
['x', 'D', 'D', 'x', 'x']
['x', 'D', 'L', 'U', 'x']
['x', 'x', 'L', 'L', 'x']
['x', 'x', 'x', 'x', 'x']
deque([(3, 2), (2, 3), (1, 2)])
(4, 2) x 0
(2, 2) L 1
(3, 3) L 2
(3, 1) x 3
['x', 'x', 'x', 'x', 'x']
['x', 'D', 'D', 'x', 'x']
['x', 'D', 'L', 'x', 'x']
['x', 'x', 'L', 'L', 'x']
['x', 'x', 'x', 'x', 'x']
deque([(2, 3), (1, 2)])
(3, 3) L 0
(1, 3) x 1
(2, 4) x 2
(2, 2) L 3
['x', 'x', 'x', 'x', 'x']
['x', 'D', 'D', 'x', 'x']
['x', 'D', 'L', 'x', 'x']
['x', 'x', 'x', 'L', 'x']
['x', 'x', 'x', 'x', 'x']
deque([(1, 2), (3, 3)])
(2, 2) L 0
(0, 2) x 1
(1, 3) x 2
(1, 1) D 3
['x', 'x', 'x', 'x', 'x']
['x', 'D', 'D', 'x', 'x']
['x', 'x', 'L', 'x', 'x']
['x', 'x', 'x', 'L', 'x']
['x', 'x', 'x', 'x', 'x']
deque([(3, 3), (2, 2), (1, 1)])
(4, 3) x 0
(2, 3) x 1
(3, 4) x 2
(3, 2) x 3
['x', 'x', 'x', 'x', 'x']
['x', 'D', 'D', 'x', 'x']
['x', 'x', 'L', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
deque([(2, 2), (1, 1)])
(3, 2) x 0
(1, 2) x 1
(2, 3) x 2
(2, 1) D 3
['x', 'x', 'x', 'x', 'x']
['x', 'D', 'D', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
deque([(1, 1), (2, 1)])
(2, 1) D 0
(0, 1) x 1
(1, 2) x 2
(1, 0) x 3
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'D', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
deque([(2, 1)])
(3, 1) x 0
(1, 1) x 1
(2, 2) x 2
(2, 0) x 3
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
['x', 'x', 'x', 'x', 'x']
deque([])

 

4. 정답 출력

answer = h*w
for i in range(1,h+1):
    for j in range(1,w+1):
        if arr[i][j] != 'x' :
            answer += -1
print(answer)

전체 h*w개 중 x가 아닌 개수들을 빼면 탈출 가능한 지점의 수이다.

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = []
for i in range(h+2):
    if i==0 or i==h+1:
        arr.append(['x']*(w+2))
    else:
        temp = list(input())
        temp = ['x'] + temp + ['x']
        arr.append(temp)

q = deque()
for i in (1,h):
    for j in range(1,w+1):
        if i==1 and arr[i-1][j] == 'x' and arr[i][j] == 'U':
            q.append((j,i))
        if i==h and arr[i+1][j] == 'x' and arr[i][j] == 'D':
            q.append((j,i))
            
for i in range(1,h+1):
    for j in (1,w):
        if j==1 and arr[i][j-1] == 'x' and arr[i][j] == 'L':
            q.append((j,i))
        if j==w and arr[i][j+1] == 'x' and arr[i][j] == 'R':
            q.append((j,i))

step = [[1,-1,0,0],[0,0,1,-1]]
while q:
    x,y = q.popleft()
    arr[y][x] = 'x'
    for i in range(4):
        nx = x + step[0][i]
        ny = y + step[1][i]

        if 0<=nx<=w+1 and 0<=ny<=h+1:
            if i==0 and arr[ny][nx] == 'L' :
                q.append((nx,ny))
            if i==1 and arr[ny][nx] == 'R' :
                q.append((nx,ny))
            if i==2 and arr[ny][nx] == 'U' :
                q.append((nx,ny))
            if i==3 and arr[ny][nx] == 'D' :
                q.append((nx,ny))

answer = h*w
for i in range(1,h+1):
    for j in range(1,w+1):
        if arr[i][j] != 'x' :
            answer += -1
print(answer)

 

코멘트

물 골3