공 굴리기 코드 질문드립니다.
294
작성한 질문수 27
클래스 사용해서 작성했는데, 계속 무한 반복을 도는 것 같습니다. 어디가 잘못된건지 잘 모르겠습니다.
import java.util.*;
class Node implements Comparable<Node>{
int x;
int y;
int c;
Node(int x,int y, int c){
this.x=x;
this.y=y;
this.c=c;
}
@Override
public int compareTo(Node o) {
return this.c - o.c;
}
}
class Main {
public static int n,m;
public static int INF = (int)1e9;
public static boolean[][] visit;
public static int[] dx = {0,0,1,-1};
public static int[][] map,dist;
public static int[] dy = {1,-1,0,0};
public static int dij(int s1,int s2,int e1, int e2) {
PriorityQueue<Node> q =new PriorityQueue<>();
q.offer(new Node(s1,s2,0));
dist[s1][s2] = 0;
while(!q.isEmpty()) {
Node tmp = q.poll();
int nowx = tmp.x;
int nowy = tmp.y;
int nowcnt = tmp.c;
if(nowcnt>dist[nowx][nowy]) continue;
for(int i=0; i<4; i++) {
int nx = nowx+dx[i];
int ny = nowy+dy[i];
while(nx>=0 && ny>=0 && nx<n && ny<m && map[nx][ny]==0) { //맵의 범위안을 만족하면 계속 같은 방향으로 이동
nx+=dx[i];
ny+=dy[i];
nowcnt++;
}
//벽에 막혔다.
nx-=dx[i]; //이전 칸으로 이동
ny-=dy[i];
nowcnt--; //이전 칸으로 이동했으니까 갯수 하나 감소
if(dist[nx][ny]>nowcnt) { //우선순위 큐에 넣기
dist[nx][ny] = nowcnt;
q.offer(new Node(nx,ny,dist[nx][ny]));
}
}
}
//답 출력
if(dist[e1-1][e2-1]==Integer.MAX_VALUE) return -1;
return dist[e1-1][e2-1];
}
public int solution(int[][] board, int[] s, int[] e){
int answer = 0;
n=board.length;
m=board[0].length;
dist = new int[n][m];
for(int i=0; i<n; i++) Arrays.fill(dist[i], INF);
map = new int[n][m];
for(int i=0; i<n; i++) {
for(int j=0; j<m;j++) {
map[i][j] = board[i][j];
}
}
answer = dij(s[0],s[1],e[0],e[1]);
return answer;
}
public static void main(String[] args){
Main T = new Main();
System.out.println(T.solution(new int[][]{{0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 0}}, new int[]{1, 0}, new int[]{4, 5}));
System.out.println(T.solution(new int[][]{{0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 2}));
System.out.println(T.solution(new int[][]{{1, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}}, new int[]{0, 3}, new int[]{4, 2}));
System.out.println(T.solution(new int[][]{{0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 1, 1, 0, 1, 1}, {0, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 5}));
System.out.println(T.solution(new int[][]{{0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}}, new int[]{0, 0}, new int[]{4, 3}));
}
}
답변 1
0
안녕하세요^^
이렇게 의도한 대로 코드가 돌지 않으면 중간중간 System.out.println()으로 특정 변수를 출력해보세요. 그러면 무엇이 문제인지 알 수 있습니다. 이 문제는 무한반복하는 문제가 발생했는데 그렇다면 무한 반복이 돌 수 있는 부분은 while(!q.isEmpty()) 문이라 예측되므로 이 구문 안에서
System.out.println(tmp.x + " " + tmp.y + " " + tmp.c);
를 해보면 알 수 있습니다. 출력을 해보면 tmp.c값이 계속 음수로 작아지면서 무한 반복하고 있음을 알 수 있습니다. 영상을 잘 보시고 nowcnt값이 잘 초기화되고 있는지 확인해보세요.
비밀번호
0
68
1
과일 가져가기 이러한 경우에는 반례가 생기지 않나요?
0
163
2
cpu 스케줄링
0
107
2
외부 문제 질문
0
122
2
가장 많이 사용된 회의실
0
118
2
심사위원 문제 시간복잡도 질문
0
127
1
현관문 출입순서
0
98
1
미로의 최단거리 통로
0
74
1
집으로 이동 문제 코드
0
125
1
채점 사이트 개설
0
161
2
송아지를 잡자
1
110
1
다익스트라 + 환승횟수
0
135
2
문제풀이 해설 질문입니다.
0
124
2
"이동 횟수" 문제가 변형된다면?
0
156
2
예제 3번의 정답이 이해가 되지 않아요 선생님 ㅜㅜ
0
249
1
"비밀번호" 문제 확인 부탁드립니다!
0
171
1
최대 길이 연속수열 질문
0
193
1
잃어버린 강아지 문제 count 관련 질문있습니다
0
204
1
바둑대회 질문입니당
0
222
1
5. "최대 길이 바이토닉 수열" 에서 설명해주신 방법과 제가 직접 구현한 방법이 달라, 확인 한번 부탁드립니다
0
311
1
알파코드 풀이질문입니다
0
218
1
7번 비밀 번호 문제에 시간복잡도가 궁금합니다!
0
164
1
혹시 이렇게 작성해도 괜찮나요?
0
287
2
문제풀이 확인 부탁드립니다.
0
246
1





