[백준] 미로 탈출하기

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

17090번: 미로 탈출하기

DFS로 해결할 수 있는 문제입니다. 현재 위치에서 시작으로 탈출이 가능한지 DFS로 탐색하게 됩니다. 만약 탈출이 가능하다면 DFS로 탐색하면서 만나는 위치들은 모두 탈출이 가능한 지점들입니다. 그러므로 해당 위치들에는 탈출이 가능하다고 체크해주고 만약에 탈출이 불가능하다면 만난 지점들은 모두 탈출이 불가능한 지점들입니다. 이렇게 탐색을 해주면서 탈출이 가능한 위치만 체크해주면 답을 얻을 수 있습니다.

 

import sys
sys.setrecursionlimit(10 ** 8)

sys.stdin = open("input.txt", "r")

CAN = 1
CANT = -1
IDK = 3

input = sys.stdin.readline

dir_map = {
    "U": 0,
    "R": 1,
    "D": 2,
    "L": 3
}

dys = [-1, 0, 1, 0]
dxs = [0, 1, 0, -1]

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

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


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

def inRange(y, x):
    return 0 <= y < n and 0 <= x < m

def dfs(y, x):
    global visited, local_visited
    # 탈출이 가능한 경우
    if not inRange(y, x):
        return CAN

    # 현재에 왔을 때 탈출이 가능하다고 되어 있는 경우
    if visited[y][x] == CAN:
        return CAN

    # 현재에 왔는데 탈출이 불가능하다고 되어 있는 경우
    if visited[y][x] == CANT:
        return CANT

    # 방문중인 위치에 다시 도달한 경우에는 탈출이 불가능하다.
    if visited[y][x] == IDK:
        visited[y][x] = CANT
        return CANT

    visited[y][x] = IDK
    dir = dir_map[board[y][x]]
    visited[y][x] = dfs(y + dys[dir], x + dxs[dir])

    return visited[y][x]

ans = 0

for i in range(n):
    for j in range(m):
        if visited[i][j] == CAN:
            ans += 1
            continue

        if visited[i][j] == CANT:
            continue

        dfs(i, j)

        if visited[i][j] == CAN:
            ans += 1


print(ans)