• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

공 굴리기 코드 질문드립니다.

23.06.16 16:20 작성 조회수 195

0

클래스 사용해서 작성했는데, 계속 무한 반복을 도는 것 같습니다. 어디가 잘못된건지 잘 모르겠습니다.

 

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값이 잘 초기화되고 있는지 확인해보세요.