[BOJ 17090 🥇3] 미로 탈출하기 (Python)

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

17090번: 미로 탈출하기

문제

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.

어떤 칸(r, c)에 적힌 문자가

• U인 경우에는 (r-1, c)로 이동해야 한다.
• R인 경우에는 (r, c+1)로 이동해야 한다.
• D인 경우에는 (r+1, c)로 이동해야 한다.
• L인 경우에는 (r, c-1)로 이동해야 한다.

미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

 

입력

첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

 

출력

첫째 줄에 탈출 가능한 칸의 수를 출력한다.

 

예제 입력 1 

3 3
DDD
DDD
DDD

 

예제 출력 1 

9

 

예제 입력 2 

3 3
DDR
DLU
LLL

 

예제 출력 2 

9

 

예제 입력 3 

3 3
RRD
RDD
ULL

 

예제 출력 3 

0

 

예제 입력 4 

3 4
RRDD
RRDR
DULU

 

예제 출력 4 

4

 

⭕ CODE

import sys

input = sys.stdin.readline

from collections import deque

def bfs(x, y):
    global count

    # x,y 방문처리
    visited[x][y] = 1
    q = deque()
    q.append((x, y))

    # 탈출 가능한지 여부 flag
    flag = False

    # 지금 bfs도는 동안 탐색한 경로를 담기위한 now
    now = []
    # 현재 지점 x,y도 now에 넣어주기
    now.append((x,y))

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

        if arr[x][y] == 'D':
            nx = x + 1
            ny = y
        elif arr[x][y] == 'U':
            nx = x - 1
            ny = y
        elif arr[x][y] == 'L':
            nx = x
            ny = y - 1
        elif arr[x][y] == 'R':
            nx = x
            ny = y + 1

        # 다음에 이동할 장소가 격자안에 존재하고 방문한적이 없다면
        if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
            # 방문처리해주고 현재 탐색할 경로 now에 추가해주기
            q.append((nx, ny))
            visited[nx][ny] = 1
            now.append((nx, ny))

        # 만약 격자 밖
        # 즉 탈출 가능하다면
        elif nx < 0 or nx >= n or ny < 0 or ny >= m:
            # count + 1 해주고
            # 탈출 가능하므로 flag 는 True로 바꿔주고 break 중단
            count += 1
            flag = True
            break

        # 다음지점 nx,ny가 check안에 존재한다면
        # 이 지점 또한 탙출 가능한 지점이므로 count + 1 해주고 flag는 True로 바꿔주고 break
        elif (nx, ny) in check:
            count += 1
            flag = True
            break

    # 만약 탈출이 불가능하다면
    # 무한 루프인것이므로
    if not flag:
        # 현재 탐색한 경로의 모든 (a,b)좌표를
        # 루프에 담아주기
        for a, b in now:
            roop.add((a,b))

    # 탈출 가능하다면
    else:
        # 현재 탐색한 경로의 모든 (a,b)좌표를
        # 탈출 가능한 경로 check에 담아주기
        for a,b in now:
            check.add((a,b))


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

arr = [list(input().rstrip()) for _ in range(n)]

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

count = 0

# 그 칸을 지났을 때 밖으로 탈출가능한 check
check = set()

# 그 칸을 지났을 때 안에서 무한 루프를 돌아 탈출 불가능한 roop
roop = set()


for i in range(n):
    for j in range(m):
        # 만약 i,j가 무한루프에 있으면 넘긴다.
        if (i,j) in roop:
            continue

        # 만약 i,j가 탈출가능한 도로에 있다면 count + 1
        if (i,j) in check:
            count += 1

        # bfs 실행
        else:
            bfs(i, j)

print(count)

✏️ Comment

탈출가능한 지점인지 불가능한 지점인지 기록을 하는것이 중요한 문제였다고 생각한다. 그러한 작업없이 모든 지점을 탐색하면 시간초과가 나게된다.