[백준 16137] 견우와 직녀

[ 백준 16137 : 견우와 직녀 ]

오랜만에 BFS문제를 풀어본것같다. 사실 문제를 읽으면서도 이게 BFS맞겠지 하고 풀었다.
왠만하면 BFS와 DFS같은 문제들은 바로 음 이렇게 풀어야지 하는데 이문제는 한글해석이 너무 어려웠다... 영문을 번역한것도 아닌데 무튼 좀 이상했다ㅋㅋㅋㅋㅋㅋ

첫번째로는 말이 이상하다.

이렇게 되면, 까치와 까마귀에게 굉장히 미안하면서도 민망해지기 때문에 견우는 오작교를 두 번 연속으로 건너는 일은 피하려고 한다.

이런 상황에서도 까마귀와 까치는 견우와 직녀를 도와주고 싶었기 때문에, 견우가 원하는 다리에서 주기가 M 분인 다리를 하나 더 놓아주겠다고 한다. 다만, 아래와 같이 절벽이 가로와 세로로 교차하는 경우에는 까마귀와 까치가 다리를 만들어 줄 수 없다고 한다.

내가 이상한건지는 모르겠는데
두번 연속으로 건너는 일은 피하려고한다. -> 이런 상황에도 까치와 까마귀는 도와준단다
-> 원하는 다리에서 주기M분인 다리를 만들어준다 -> 절벽이 가로세로 교차시엔 안만들어준다.

어떤때는 다리라고하고 어떤때는 오작교라고 하고 처음에 푼게 틀렸다고 나와서 두개가 다른건줄 알았다.

1.그리고 다리에서 M인 다리를 하나 더 놓아준다는게 이미 초기 인풋에 있는 다리에서 이어지는 다리를 만들어준다는 건가????? 이렇게 생각했고
5 5
1 1  0 1   1
2 1  1 0 20
0 4  1 0   0
0 0  1 1   1
0 1  1 1   1

2.절벽이 가로와 세로로 교차하는 경우에는 다리를 만들어주지 못한다했으니
5 5
1 1  0 1   1
2 0  1 0 20
0 4  1 0   0
0 0  1 1   1
0 1  1 1   1

이런 경우에  는 (1행,2열)의 0에는 다리를 만들수있다는거라 생각했고


또 뭔가 빠진게 견우가 움직이는 시간이다.
견우는 상하좌우 로만 움직일 수 있고 한 칸 이동하는데 1의 시간이 소요된다는 점도 빠져있다. 그래서 1-> 1 이동은 0초인건가????
별의별 생각을 다했는데
방문했는지 안했는지 처리를 잘못해서 계속 틀리는 거였다.

결론으로는 1. 그림은 못만든다. 무조건 만들어준 다리든 원래 있던 다리든 오작교든
다리에서 다리로는 못가게 처리했고
2. 그림은 만들수있게했다. 절벽만 크로스 될때 다리를 못만들게 처리헸다.

맵을 인풋받고 초기에 절벽이 크로스 되는 지점들을 모두 -1로 만들었다.


이제 bfs를 돌렸는데
Queue에 넣을 원소로는 x좌표,y좌표,현재까지의 시간, 만든 다리를 건넜는지 체크

상하좌우를 살펴보면서
1. 현재 1에 있을때 다음이 1이고 방문배열의 값이 현재까지시간+1보다 클때 큐 삽입
2. 현재 1에 있을때 다음이 0이고 만든 다리를 안건넜다면 배수 시간으로 큐 삽입
3. 현재 0에 있을때 다음은 1이고 방문배열의 값이 현재까지시간+1보다 클때 큐 삽입
4. 현재 1에 있을때 다음이 2 이상이고 배수 시간으로 큐 삽입
5. 현재 2 이상이고 다음이 1일때 방문배열의 값이 현재까지시간+1보다 클때 큐 삽입