프로그래민👨‍💻

최단거리를 구하는 문제이기에 BFS를 사용하는 문제이다. 이 문제에선 신경써야할 점이 두가지 있다. 첫째, visit[][][]을 이용하여 벽을 뚫지 않은 상태에서랑 벽을 이미 한번 뚫은 상태에서 방문이 가능한지 신경써줘야한다. 둘째, queue에서 poll 할때 목적지 지점이면 최솟값으로 갱신 가능한지 확인하는 것 이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 ..

BFS를 사용하는 문제이다. 모든 시작점 1을 queue에 집어넣은 다음 평소 boolean배열 형태로 사용하던 visit를 int배열 형태로 바꾸어 토마토가 익은 날짜로 대신하여 사용하였다. 그리고 이미 visit배열이 갱신되었더라도 더 작은 날짜를 가질 수 있다면 갱신할수 있도록 while문 안쪽에서 구현하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 7..

BFS를 두번 사용할 계획을 세웠다. 첫번째 BFS를 통하여 모든 악마를 찾아 스킬이 도달하는 최단시간을 visitForDevil 배열에 저장해주었다. 그 후 두번째 BFS를 통해 S의 위치를 찾아 S가 n초 후에 도달할 수 있는 .의 위치에서 visitForDevil의 시간을 비교하여 도달여부를 결정하였다. 이런식으로 D를 찾으면 종료하였고, 못 찾으면 GameOver를 해주었다. 그렇지만 두번 BFS를 도는 방법 말고도, 구분자를 사용하여 악마와 S를 하나의 BFS에서 처리할 수 있는 방법도 있다.(단, 악마가 queue에 S보다 먼저 들어가 있어야함). 이 방법은 코드를 더 짧게 해주고, 시간도 더 줄여줄 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1..