백준 / 미로 탈출하기 / 17090번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 미로 탈출하기 / 17090번 (골드 3단계)

문제 사이트: https://www.acmicpc.net/problem/17090

 

문제 설명

---

나의 풀이

import sys

input = sys.stdin.readline  # 입력을 더 빠르게 받기 위한 설정

sys.setrecursionlimit(350000)  # 재귀 호출 깊이 제한을 늘려 스택 오버플로 방지

def inrange(r, c, R, C):
    """
    주어진 좌표 (r, c)가 미로의 범위 안에 있는지 확인하는 함수
    """
    if 0 <= r < R and 0 <= c < C:
        return True
    return False

def dfs(r, c, R, C):
    """
    깊이 우선 탐색 함수
    :param r: 현재 행
    :param c: 현재 열
    :param R: 미로의 행 수
    :param C: 미로의 열 수
    :return: 해당 좌표에서 탈출 가능한지 여부 (True: 탈출 가능, False: 탈출 불가)
    """
    global ans
    check[r][c] = 2  # 방문 체크 (2: 방문했지만 탈출 불가)
    v = maze[r][c]  # 현재 칸의 이동 방향
    nr, nc = r + direction[v][0], c + direction[v][1]  # 다음 이동할 좌표 계산

    # 미로 밖으로 나가면 탈출 가능
    if not inrange(nr, nc, R, C):
        check[r][c] = 1  # 방문 체크 (1: 탈출 가능)
        return True

    # 다음 칸이 이미 탈출 가능으로 표시되어 있으면 현재 칸도 탈출 가능
    if check[nr][nc] == 1:
        check[r][c] = 1
        return True
    # 다음 칸이 이미 탈출 불가능으로 표시되어 있으면 현재 칸도 탈출 불가
    elif check[nr][nc] == 2:
        return False

    # 재귀 호출을 통해 다음 칸을 탐색
    if dfs(nr, nc, R, C):
        check[r][c] = 1
        return True
    return False

N, M = map(int, input().split())  # 미로의 행과 열 입력

maze = [input().rstrip() for _ in range(N)]  # 미로 정보 입력

direction = {'U': (-1, 0), 'D': (1, 0), 'R': (0, 1), 'L': (0, -1)}  # 이동 방향

check = [[0] * M for _ in range(N)]  # 방문 여부를 저장하는 2차원 배열

# 모든 칸에 대해 DFS 탐색 수행
for r in range(N):
    for c in range(M):
        if not check[r][c]:
            dfs(r, c, N, M)

# 탈출 가능한 칸의 개수 세기
answer = 0
for r in range(N):
    for c in range(M):
        if check[r][c] == 1:
            answer += 1
print(answer)

---

※ 알아야 할 것

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

아기상어 문제랑 비슷한 느낌이다.