글 읽기 - 92%에서 계속 틀립니다 반례나 틀린코드 있을까요?

wnsxo202 5년 전 0

bfs로 풀었습니다.. 고수님들 헬프 좀 부탁드려용

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

public class Main {
	static int N, M, K, map[][][], ar, ac, res;
	static boolean visited[][][];
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };
	static Queue<Node> q = new LinkedList<>();

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

		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		map = new int[N][M][K + 1];
		visited = new boolean[N][M][K + 1];
		String line;

		for (int i = 0; i < N; i++) {
			line = sc.next();
			for (int j = 0; j < M; j++) {
				map[i][j][0] = line.charAt(j) - '0';
				if (map[i][j][0] == 1) {
					visited[i][j][0] = true;
				}
			}
		}
		setMap();

		bfs(0, 0);

		findRes();
		System.out.println(res);
	}

	private static void bfs(int y, int x) {
		q.add(new Node(y, x, 1, K));
		visited[y][x][K] = true;

		while (!q.isEmpty()) {
			Node temp = q.poll();
			int r = temp.r;
			int c = temp.c;
			int cnt = temp.cnt;
			int state = temp.state;

			for (int i = 0; i < 4; i++) {
				ar = r + dy[i];
				ac = c + dx[i];

				if (ar >= 0 && ac >= 0 && ar < N && ac < M) {
					if (state != 0) { // 벽을 부술 수 있고
						if (map[ar][ac][state] == 1) { // 벽을 만난다면
							q.add(new Node(ar, ac, cnt + 1, state - 1)); // 상태를 -1하고 벽을 부수고 들어감
							map[ar][ac][state - 1] = cnt + 1;
						} else if (!visited[ar][ac][state]) { // 벽이 아니고 방문하지 않았다면
							q.add(new Node(ar, ac, cnt + 1, state)); // 다음 점으로 통과
							visited[ar][ac][state] = true;
							map[ar][ac][state] = cnt + 1;
						}
					} else {
						if (!visited[ar][ac][state]) { // 벽을 부술 수 없고 방문하지 않았다면
							q.add(new Node(ar, ac, cnt + 1, state));
							visited[ar][ac][state] = true;
							map[ar][ac][state] = cnt + 1;
						}
					}
				}
			}

		}

	}

	public static void findRes() {
		res = Integer.MAX_VALUE;

		for (int i = 0; i < K; i++) {
			if (map[N - 1][M - 1][i] != 0) {
				res = Math.min(res, map[N - 1][M - 1][i]);
			}
		}

		if (res == Integer.MAX_VALUE) {
			if (N == 1 && M == 1)
				res = 1;
			else
				res = -1;
		}
	}

	public static void setMap() {
		for (int k = 0; k < K; k++) {
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j][k + 1] = map[i][j][0];
					visited[i][j][k + 1] = visited[i][j][0];
				}
			}
		}

	}

	static class Node {
		int r, c, cnt, state;

		public Node(int r, int c, int cnt, int state) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
			this.state = state;
		}
	}
}

jjiiyyuu 4년 전 0

코드를 전부 보지는 않았지만, findRes()에서 i<=k까지 검사하지 않는 문제가 있습니다.

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

문제

문제

출처

ICPC

92%에서 계속 틀립니다 반례나 틀린코드 있을까요?

wnsxo202 5년 전 0

jjiiyyuu 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말