선생님 저 코드에서 최단거리인지 판별하는 것은

Question

선생님 저 코드에서 최단거리인지 판별하는 것은 dis[7][7]에 어떤 수가 들어가면 바로 코드가 종료되는 조건도 없는데 어떻게 판별하는 것인가요...? 이 문제는 도착지점까지 도착하는 경로가 2개 뿐이라서 while(!Q.isEmpty()) 이 조건때문에 둘 중에 먼저 도착하면 자동으로 다른 경로를 계산할 때, Queue가 비어있게 되어서 반복문이 종료되어서 그게 가능하지만 도착하는 경로가 3개 이상일 경우에는 불가능 할 것 같은데 그때는 따로 조건을 추가해줘야 되나요...?

luckych · Answer

같은 궁금증이 있던 수강생입니다. 성찬우님 댓글 읽고 이해가 갔네요 감사합니다. 큐의 특성상 먼저 들어간 것이 먼저 나오므로 최단 거리에서 도착지점이 1로 바뀌고 그 후에는 if문에서 걸러져서 카운트 되지 않겠네요. DFS, 재귀함수만 계속 보다보니 헷갈렸나봅니다..ㅠㅠ

dngkdn2446 · Answer

같은 수강자의 생각입니다.. 정말 참고만 바래요 ㅠㅠ .. 1. 종료가 되는 조건. Q) dis[7][7]에 어떤 수가 들어가면 바로 코드가 종료되는 조건도 없는데 어떻게 판별하는 것인가요...? A) 종료가 되는 조건은 while(q가 비엇을경우)입니다. 그리고 q(Queue)에 새로운 Point객체를 넣는 조건은 " if ( nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && board [ nx ][ ny ] == 0 ) " 입니다. board[nx][ny] 마지막엔 [7][7]이 0이여야 q에 새로운 Point객체가 들어갈 수 있지만 이미 도착한 nx,ny가 있다면 1이 되므로 늦은 nx,ny는 공중분해 됩니다. (if 에 걸리지 않아서 q에 들어가지 않기때문) 2. 경로가 3개 이상? 각각의 경로는 각각 if문을 통해 q에 넣고 이를 다시 while문으로 돌리는 상황입니다. 그렇기 때문에 q에 넣은 x,y값을 재 사용하는 것이죠. 또한 경로가 겹치는데 정답인 제일 짧은 경로가 늦게 올경우 즉 이미 board[nx][ny]값이 1이여서 q에 못들어가는 경우? 는 없습니다. 정답(짧은 경로)을 위해 거쳐야하는 구간은 어쨋든 먼저 1로 만든 nx,ny경로가 제일 짧은 경로입니다. dis배열을 이용하고 board[nx][ny]를 1로 바꾸는 이유입니다. 다른 늦은 경로들은 사전에 if문으로 걸러내는겁니다. 많이 부족하고 저도 잘 모르겟지만.. 화이팅!

alstjr7064430 · Answer

선생님들 댓글 보고 이해 했습니다 감사합니다.