글 읽기 - 어디가 틀린건지 알수가 없습니다.

jihea37 7년 전 0

예시는 다 잘 작동하는데 아예 틀렸다고 나옵니다.

왜그런걸까요?

다익스트라로 풀었습니다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

class Node implements Comparable<Node> {
	int x;
	int y;
	int dir;
	int count;

	public Node() {

	}

	public Node(int x, int y, int dir, int count) {
		this.x = x;
		this.y = y;
		this.dir = dir;
		this.count = count;
	}

	@Override
	public int compareTo(Node o) {
		if (this.count > o.count) {
			return 1;
		} else if (this.count == o.count) {
			return 0;
		} else {
			return -1;
		}
	}
}

class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();

		int[][] maze = new int[n + 1][m + 1];
		int[][][] count = new int[n + 1][m + 1][5];
		boolean[][][] visited = new boolean[n + 1][m + 1][5];

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				maze[i][j] = sc.nextInt();
				count[i][j][1] = Integer.MAX_VALUE;
				count[i][j][2] = Integer.MAX_VALUE;
				count[i][j][3] = Integer.MAX_VALUE;
				count[i][j][4] = Integer.MAX_VALUE;
			}
		}

		Node start = new Node(sc.nextInt(), sc.nextInt(), sc.nextInt(), 0);
		Node fin = new Node(sc.nextInt(), sc.nextInt(), sc.nextInt(),
				Integer.MAX_VALUE);

		PriorityQueue<Node> queue = new PriorityQueue<Node>();
		count[start.x][start.y][start.dir] = 0;
		queue.offer(start);

		while (!queue.isEmpty()) {
			Node now;

			do {
				now = queue.poll();
			} while (!queue.isEmpty() && visited[now.x][now.y][now.dir] == true);

			visited[now.x][now.y][now.dir]=true;
//			System.out.println(now.x + " , "+now.y+ " , "+now.dir + " , "+now.count);
			
			Node tmp = new Node(now.x, now.y, now.dir, now.count);

			// 오른쪽으로 회전
			if (now.dir == 1) {
				tmp.dir = 3;
			} else if (now.dir == 2) {
				tmp.dir = 4;
			} else if (now.dir == 3) {
				tmp.dir = 2;
			} else {
				tmp.dir = 1;
			}
			if (count[tmp.x][tmp.y][tmp.dir] > count[now.x][now.y][now.dir] + 1) {
				count[tmp.x][tmp.y][tmp.dir] = count[now.x][now.y][now.dir] + 1;
				tmp.count = count[tmp.x][tmp.y][tmp.dir];
				queue.offer(tmp);
//				System.out.println("add: "+tmp.x + ", "+tmp.y+", "+ tmp.dir);
			}

			tmp = new Node(now.x, now.y, now.dir, now.count);
			
			// 왼쪽으로 회전
			if (now.dir == 1) {
				tmp.dir = 4;
			} else if (now.dir == 2) {
				tmp.dir = 3;
			} else if (now.dir == 3) {
				tmp.dir = 1;
			} else {
				tmp.dir = 2;
			}
			if (count[tmp.x][tmp.y][tmp.dir] > count[now.x][now.y][now.dir] + 1) {
				count[tmp.x][tmp.y][tmp.dir] = count[now.x][now.y][now.dir] + 1;
				tmp.count = count[tmp.x][tmp.y][tmp.dir];
				queue.offer(tmp);
//				System.out.println("add: "+tmp.x + ", "+tmp.y+", "+ tmp.dir);
			}

			// 직진 1, 2, 3
				int i=1;
				tmp = new Node(now.x, now.y, now.dir, now.count);
				
				if (now.dir == 1 && now.y + i <= m
						&& maze[now.x][now.y + i] != 1) {
					tmp.y = now.y + i;
				} else if (now.dir == 2 && now.y - i > 0
						&& maze[now.x][now.y - i] != 1) {
					tmp.y = now.y - i;
				} else if (now.dir == 3 && now.x + i <= n
						&& maze[now.x + i][now.y] != 1) {
					tmp.x = now.x + i;
				} else if (now.dir == 4 && now.x - i > 0
						&& maze[now.x - i][now.y] != 1) {
					tmp.x = now.x - i;
				}
				if (count[tmp.x][tmp.y][tmp.dir] > count[now.x][now.y][now.dir] + 1) {
					count[tmp.x][tmp.y][tmp.dir] = count[now.x][now.y][now.dir] + 1;
					tmp.count = count[tmp.x][tmp.y][tmp.dir];
					queue.offer(tmp);
//					System.out.println("add: "+tmp.x + ", "+tmp.y+", "+ tmp.dir);
				}
				
				
				i=2;
				tmp = new Node(now.x, now.y, now.dir, now.count);
				
				if (now.dir == 1 && now.y + i <= m
						&& maze[now.x][now.y + 1] != 1 && maze[now.x][now.y+i]!=1) {
					tmp.y = now.y + i;
				} else if (now.dir == 2 && now.y - i > 0
						&& maze[now.x][now.y - i] != 1 && maze[now.x][now.y-1]!=1) {
					tmp.y = now.y - i;
				} else if (now.dir == 3 && now.x + i <= n
						&& maze[now.x + i][now.y] != 1 && maze[now.x+1][now.y]!=1) {
					tmp.x = now.x + i;
				} else if (now.dir == 4 && now.x - i > 0
						&& maze[now.x - i][now.y] != 1&& maze[now.x-1][now.y]!=1) {
					tmp.x = now.x - i;
				}
				if (count[tmp.x][tmp.y][tmp.dir] > count[now.x][now.y][now.dir] + 1) {
					count[tmp.x][tmp.y][tmp.dir] = count[now.x][now.y][now.dir] + 1;
					tmp.count = count[tmp.x][tmp.y][tmp.dir];
					queue.offer(tmp);
//					System.out.println("add: "+tmp.x + ", "+tmp.y+", "+ tmp.dir);
				}
				
				
				i=3;
				tmp = new Node(now.x, now.y, now.dir, now.count);
				
				if (now.dir == 1 && now.y + i <= m
						&& maze[now.x][now.y + 1] != 1 && maze[now.x][now.y+i]!=1&& maze[now.x][now.y+2]!=1) {
					tmp.y = now.y + i;
				} else if (now.dir == 2 && now.y - i > 0
						&& maze[now.x][now.y - i] != 1 && maze[now.x][now.y-1]!=1&& maze[now.x][now.y-2]!=1) {
					tmp.y = now.y - i;
				} else if (now.dir == 3 && now.x + i <= n
						&& maze[now.x + i][now.y] != 1 && maze[now.x+1][now.y]!=1&& maze[now.x+1][now.y]!=1) {
					tmp.x = now.x + i;
				} else if (now.dir == 4 && now.x - i > 0
						&& maze[now.x - i][now.y] != 1&& maze[now.x-1][now.y]!=1&& maze[now.x-2][now.y]!=1) {
					tmp.x = now.x - i;
				}
				if (count[tmp.x][tmp.y][tmp.dir] > count[now.x][now.y][now.dir] + 1) {
					count[tmp.x][tmp.y][tmp.dir] = count[now.x][now.y][now.dir] + 1;
					tmp.count = count[tmp.x][tmp.y][tmp.dir];
					queue.offer(tmp);
//					System.out.println("add: "+tmp.x + ", "+tmp.y+", "+ tmp.dir);
				}
				

//				System.out.println("-----------------");
				

			}
		System.out.println(count[fin.x][fin.y][fin.dir]);
	}

}

zlzmsrhak 7년 전 0

반례입니다.

이런 식으로 ctrl C, V와 약간의 수정으로 코드를 작성하시면 오타를 찾기 매우 힘들 수 있기 때문에,

되도록이면 반복문이나 재귀, 함수 재정의 등으로 반복되는 부분을 없애는 것이 좋습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀린건지 알수가 없습니다.

jihea37 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말