[BOJ] 2206

less than 1 minute read

벽 부수고 이동하기

2206번 https://www.acmicpc.net/problem/2206

DFS로 모든 경우를 다 확인해볼 수도 있지만 그렇게 한다면 시간초과가 날 가능성이 높습니다.
벽을 부수고 가지 않으면서 각 칸들로의 시작점, 도착점으로부터의 거리를 구합니다.
그 후 벽과 인접한 네 곳 중에서
시작점과 가장 가까운 곳의 시작점으로부터의 거리 + 도착점과 가장 가까운 곳의 도착점으로부터의 거리 + 1
가 그 벽을 부수고 가는 거리임을 이용하면 됩니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/2206.cpp

Categories:

Updated:

Leave a comment