인프런 커뮤니티 질문&답변
작성한 질문수
선생님 저 코드에서 최단거리인지 판별하는 것은
작성
·
308
1
선생님 저 코드에서 최단거리인지 판별하는 것은 dis[7][7]에 어떤 수가 들어가면 바로 코드가 종료되는 조건도 없는데 어떻게 판별하는 것인가요...?
이 문제는 도착지점까지 도착하는 경로가 2개 뿐이라서 while(!Q.isEmpty()) 이 조건때문에 둘 중에 먼저 도착하면 자동으로 다른 경로를 계산할 때, Queue가 비어있게 되어서 반복문이 종료되어서 그게 가능하지만 도착하는 경로가 3개 이상일 경우에는 불가능 할 것 같은데 그때는 따로 조건을 추가해줘야 되나요...?
답변 3
2
같은 궁금증이 있던 수강생입니다.
성찬우님 댓글 읽고 이해가 갔네요 감사합니다.
큐의 특성상 먼저 들어간 것이 먼저 나오므로 최단 거리에서 도착지점이 1로 바뀌고 그 후에는 if문에서 걸러져서 카운트 되지 않겠네요.
DFS, 재귀함수만 계속 보다보니 헷갈렸나봅니다..ㅠㅠ
1
같은 수강자의 생각입니다.. 정말 참고만 바래요 ㅠㅠ ..
1. 종료가 되는 조건.
Q)dis[7][7]에 어떤 수가 들어가면 바로 코드가 종료되는 조건도 없는데 어떻게 판별하는 것인가요...?
A) 종료가 되는 조건은 while(q가 비엇을경우)입니다. 그리고 q(Queue<Point>)에 새로운 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문으로 걸러내는겁니다.
많이 부족하고 저도 잘 모르겟지만.. 화이팅!
0