[백준] 실버1 쉬운 최단거리

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

14940번: 쉬운 최단거리

본 문제를 위한 알고리즘은 bfs인것은 확실하다. 

문제 내용부터 모든 지점에 대해서 목표지점까지의 거리를 구하라고 하기 때문이다.

 

하지만, 목표지점이 모든 예제에 대해서 일정한게 아닌 다른 목표지점이 되기때문에 갑자기 생각이 복잡해졌다.

 

막상, 풀고보니 굳이 복잡하게 안해도 bfs가 강력해서 알아서 다 해줬다.

 

복잡한 이유는 원래대로의 bfs 풀때는 왼쪽 맨 위부터 순차적으로 원하는 탐색지점이 있을때 쭉 탐색해나가는 식이라면 본 문제는 탐색하고자 하는 위치가 배열의 중앙에 위치할 수도 있어서 순차적으로 할 수 없기때문이다. 

 

이러한 문제는 dy, dx를 이용하면 쉽게 풀릴 수 있었다. 

 

먼저, 목표지점의 x,y 좌표를 찾은 다음 그 위치에 대해 bfs를 수행한다. 그러면 끝이다! 

 

하지만, 그전에 탐색이 불가능한 위치는 -1로 세팅해야한다. 그리고 마지막 탐색이 끝난 뒤 원래 장애물이였던 위치는 0으로 바꿔줘야한다. 

 

처음 풀이때는 탐색 불가능한 위치를 -1로 세팅하는 것을 안해줘서 틀렸지만, 다시 세팅해주고 제출해보니 성공하였다.

두번째 시도(성공)

코드가 긴 이유는 이중 for문이 너무 많이 써져서...그런거같다(더 효율적인 풀이가 있을 것 같지만 귀찮아서 안봄)