글 읽기 - 왜 자꾸 틀리는지 모르겠어요..ㅠㅠ

jihea37 6년 전 0

다익스트라로 풀고있습니다.

어디가 틀린건가요?

예시로는 잘 작동합니다.

import java.util.LinkedList;
import java.util.Scanner;

class Node {
	int x;
	int y;

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

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[m + 1][n + 1];
		boolean[][] visited = new boolean[m + 1][n + 1];
		int[][] count = new int[m + 1][n + 1];

		String data;

		for (int i = 1; i <= m; i++) {
			data = sc.next();
			for (int j = 1; j <= n; j++) {
				maze[i][j] = Character.getNumericValue(data.charAt(j - 1));
				count[i][j] = Integer.MAX_VALUE;
			}
		}
		// System.out.println("test");

		LinkedList<Node> queue = new LinkedList<Node>();
		queue.addLast(new Node(1, 1));
		visited[1][1] = true;
		count[1][1] = 0;

		while (!queue.isEmpty()) {
			Node now = queue.poll();
//			System.out.println("now = (" + now.x + " , " + now.y + ")");
//			System.out.println(count[now.x][now.y]);

			if (now.x - 1 > 0) {
				if (visited[now.x - 1][now.y] == false) {
					visited[now.x - 1][now.y] = true;
					queue.addLast(new Node(now.x - 1, now.y));
				}
				if (maze[now.x - 1][now.y] == 1) {
					count[now.x - 1][now.y] = Math.min(count[now.x - 1][now.y],
							count[now.x][now.y] + 1);
				} else {
					count[now.x - 1][now.y] = Math.min(count[now.x - 1][now.y],
							count[now.x][now.y]);
				}
			}
			
			if (now.x + 1 <= m) {
				if (visited[now.x + 1][now.y] == false) {
					visited[now.x + 1][now.y] = true;
					queue.addLast(new Node(now.x + 1, now.y));
				}
				if (maze[now.x + 1][now.y] == 1) {
					count[now.x + 1][now.y] = Math.min(count[now.x + 1][now.y],
							count[now.x][now.y] + 1);
				} else {
					count[now.x + 1][now.y] = Math.min(count[now.x + 1][now.y],
							count[now.x][now.y]);
				}
			}

			if (now.y - 1 > 0) {
				if (visited[now.x][now.y - 1] == false) {
					visited[now.x][now.y - 1] = true;
					queue.addLast(new Node(now.x, now.y - 1));
				}
				if (maze[now.x][now.y - 1] == 1) {
					count[now.x][now.y - 1] = Math.min(count[now.x][now.y - 1],
							count[now.x][now.y] + 1);
				} else {
					count[now.x][now.y - 1] = Math.min(count[now.x][now.y - 1],
							count[now.x][now.y]);
				}
			}
			
			if (now.y + 1 <= n) {
				if (visited[now.x][now.y + 1] == false) {
					visited[now.x][now.y + 1] = true;
					queue.addLast(new Node(now.x, now.y + 1));
				}
				if (maze[now.x][now.y + 1] == 1) {
					count[now.x][now.y + 1] = Math.min(count[now.x][now.y + 1],
							count[now.x][now.y] + 1);
				} else {

					count[now.x][now.y + 1] = Math.min(count[now.x][now.y + 1],
							count[now.x][now.y]);
				}
			}

		}

		System.out.println(count[m][n]);
	}
}

zlzmsrhak 6년 전 1

35번째 줄에서 우선순위큐가 아닌 그냥 큐를 사용하셨기 때문에, 현재 코드는 BFS 성향이 강합니다.

반례 확인해보세요.

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

문제

문제

출처

ICPC

왜 자꾸 틀리는지 모르겠어요..ㅠㅠ

jihea37 6년 전 0

zlzmsrhak 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말