[백준 17090] 미로 탈출하기

1. 문제

www.acmicpc.net/problem/17090

17090번: 미로 탈출하기

2. 접근 방법

visit 체크를 어떻게 할까 정말 많은 고민이 있었는데요

lovelyunsh.tistory.com/123

[백준] 17090 미로 탈출하기

이 글과 유사하게 접근했습ㄴㅣ다

 

중요한 건

갈 수 있냐 없냐를 board에 체크하는 것 !

 

원래는 재귀하면서 이제까지 거쳐온 곳들을 다 담아놓으려고 했는데, 고렇게 하면 시간 초과가 납니다

왜냐하면...tmi

인자에다가 지나온 좌표 list를 담아놓고 고것을 for해서 하나씩 방문 여부, 갈 수 있는지 없는지 여부를 넣어주려고 했단 말이죠

 

왜 이렇게 푸려고 했냐구여 ?

저두 몰라여 ㅎㅋ

 

3. 코드

python

import sys
sys.setrecursionlimit(10**9)

def dfs(x, y):
    if x < 0 or x >= M or y < 0 or y >= N:
        return True

    if board[y][x] == 'true':
        return True
    elif board[y][x] == 'false':
        return False

    if visited[y][x]:
        return False
    else:
        visited[y][x] = True
        dx, dy = dir[board[y][x]]
        tx = x + dx
        ty = y + dy

        result = dfs(tx, ty)
        board[y][x] = ('true' if result else 'false')
        return result

N, M = map(int, sys.stdin.readline().rstrip().split())
board = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
visited = [[False]*M for _ in range(N)]
dir = {'U': [0, -1], 'R': [1, 0], 'D': [0, 1], 'L': [-1, 0]}

cnt = 0
for y in range(N):
    for x in range(M):
        if dfs(x, y):
            cnt += 1

print(cnt)

4. 마치며

sys.setrecursionlimit()을 사용해서

재귀범위를 많이 늘려줘야합니다 ....

안쓰면 오류가 납니다

 

생각보다 이 문제는 python 코드가 없더라구욧 ,,

python으로 푸시는 분들께 많은 도움이 되었길 바라며

 

여튼 무튼 아직 알고리즘 푸는 실력이 많이 모자라는 것을 느낄 수 있는 문제였습니다.

 

뒤져따 나 D-10