프로그래머스. 경주로 건설

https://programmers.co.kr/learn/courses/30/lessons/67259?language=cpp 

코딩테스트 연습 - 경주로 건설

 

bfs 알고리즘으로 푸는데 주의할점이 있다.

 

1.

일반적으로 bfs 알고리즘은 방문한곳을 체크해놓고 이미 방문한곳은 다시 방문하지 않도록 하는데

이전에 풀었던 리틀 프렌즈 사천성(https://tose33.tistory.com/442)과 비슷하게 이 문제에서도 이미 방문한곳도 다시 방문할수 있어야한다.

이유는 가장 빠른 경로를 구하는것이 아닌 드는 요금의 최솟값을 구하는것이고, 요금은 코너의 수가 적을수록 줄어들기 때문이다. 

그런데 이미 방문한곳을 다시 방문하지 않도록 코드를 짜면 이미 방문했던 곳에서 있을수 있는 경로들 중 코너가 적은 경로가 있을수있는데 그 가능성이 차단된다. 

 

2.

하지만 어떤 방식으로든 방문여부를 체크는 해야되는데 그렇지 않으면 같은 장소를 무한히 돌기 때문이다.

다음 지점으로 이동할지 말지 판단은 다음 지점으로 이동했을때의 요금을 계산하고,

그 요금보다 다음 지점에 기록되어 있는 요금이 크다면 이동하면된다. (최솟값을 구하기 때문에)

 

3.

여기까지 했는데 25번 테스트케이스에서 틀렸다.

아무리 생각해도 모르겠어서 찾아봤는데 내 코드랑 거의 같아서 더 찾아보니 알고보니 25번 테케는 문제에 잘못된 점이 있어서 최근에 추가된 테스트케이스였다.

이유는 다음과 같다.

 

	1	1	1
		1
1				1
	1	1

위와 같이 맵이 주어졌을때 출발지점에서 도착지점에 도달하는 방법은 두가지가 있다.

오른쪽으로 출발과 아래로 출발이다.

 

오른쪽 출발: red 

아래로 출발: yellow 

	100	200	300	400
100	1	1	1	1000
200	800	1	1700	1100
1	1400	2000	2100 2300	1
	1	1	2700 2400	3300 3000

 

(3,3) 지점에서 문제가 발생한다.

만약 아래로 출발한 루트에서 기록한 2100원이 이미 (3,3)에 기록되어 있다면

그 다음에 오른쪽 출발한 루트에서는 (3,3)이 2300원이므로 무시된다. 

그런데 그 뒤를 보면 코너의 존재여부 때문에 결국 오른쪽 출발 루트가 3000원, 아래 출발 루트가 3300원으로 오른쪽 출발 루트가 더 싸다.

하지만 이미 (3,3)에서 오른쪽 출발루트는 막혔으므로 답은 3300원이 되버린다.

 

 

해결방법은 방문여부를 체크하는 배열을 bool mark[30][30][4] 이런식으로 만든다.

그리고 다음 지점에 기록되어있는 가격이 더 비쌀때 이동하는 방식으로 하지말고,

다음 지점에, 다음 지점으로 이동하는 방향으로 방문 안했다면 무조건 방문하면 된다.