-
백준(BOJ) 17090번 미로 탈출하기알고리즘 풀이/백준(Boj) 2020. 1. 16. 03:15
문제 : 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)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한
www.acmicpc.net
풀이 :
기본적으로 방문을 시작했을 때 ret = 0으로 두어서 방문할 수 없는 상태를 만든다.
이는 사이클으로 무한루프를 방지해준다.
동적 계획법을 통해 한 경로가 탈출 가능하다면 그 경로 과정에 있는 좌표들도 모두 탈출 가능하다는
뜻이므로 그 좌표들은 다시 탐색할 필요가 없게 만들자.
코드 ( C++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 16974번 레벨 햄버거 (0) 2020.01.18 백준(BOJ) 16957번 체스판 위의 공 (0) 2020.01.16 백준(BOJ) 17088번 등차수열 변환 (0) 2020.01.12 백준(BOJ) 16964번 DFS 스페셜 (0) 2020.01.11 백준(BOJ) 16954번 움직이는 미로 탈출 (0) 2020.01.07