글 읽기 - 으아... ㅠ 질문게시판 테스트케이스는 거의다 돌려봤는데ㅠㅠ

gongbea 6년 전 0

질게에 있는 테스트케이스는 거진 다 돌려본거 같습니다. ㅠㅠ 다 올바른 정답이 나오구요 ㅠ

2일째 붙잡고 있는데 이유를 모르겠습니다. ㅠ

import java.util.*;

class Main {
	static int[][] map;
	static int x;
	static int y;
	static int visited[][];

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		Queue<int[]> que = new LinkedList<int[]>();
		x = sc.nextInt();
		y = sc.nextInt();
		sc.nextLine();
		map = new int[y][x];
		visited = new int[y][x];
		for (int i = 0; i < y; i++) {
			String tmp[] = sc.nextLine().split(" ");
			for (int j = 0; j < x; j++) {
				map[i][j] = Integer.parseInt(tmp[j]);
				if (map[i][j] == 1) {
					int[] tmpQ = { i, j };
					visited[i][j] = 1;
					que.add(tmpQ);
				}
			}
		}
		boolean flag = true;
		for (int i = 0; i < y; i++) {
			for (int j = 0; j < x; j++) {
				if (map[i][j] == 0) {
					flag = false;
				}
			}
		}
		if (flag) {
			System.out.println(0);
			return;
		}
		BFS(que);

	}

	public static void BFS(Queue<int[]> que) {
		int last = 0;
		while (!que.isEmpty()) {
			int tm[] = que.poll();
			int nowY = tm[0];
			int nowX = tm[1];
			int dx[] = { 0, 1, 0, -1 };
			int dy[] = { -1, 0, +1, 0 };
			for (int i = 0; i < 4; i++) {
				if (inRange(nowY + dy[i], nowX + dx[i])
						&& visited[nowY + dy[i]][nowX + dx[i]] == 0
						&& map[nowY + dy[i]][nowX + dx[i]] == 0) {
					visited[nowY + dy[i]][nowX + dx[i]] = visited[nowY][nowX] + 1;
					last = visited[nowY][nowX] + 1;
					int tmN[] = { nowY + dy[i], nowX + dx[i] };
					que.offer(tmN);

				}
				if (inRange(nowY + dy[i], nowX + dx[i])
						&& visited[nowY + dy[i]][nowX + dx[i]] == 0
						&& map[nowY + dy[i]][nowX + dx[i]] == -1) {
					visited[nowY + dy[i]][nowX + dx[i]] = -1;
				}
			}

		}
		boolean flag = true;
		for (int i = 0; i < y; i++) {
			for (int j = 0; j < x; j++) {
				if (visited[i][j] == 0) {
					flag = false;
				}
			}
		}

		if (flag)
			System.out.println(last - 1);
		else {
			System.out.println(-1);
		}
	}

	public static boolean inRange(int _y, int _x) {
		if (_x < x && _x >= 0 && _y < y && _y >= 0) {
			return true;
		}
		return false;
	}
}

3587jjh 6년 전 1

반례:

4 4

-1 -1 -1 0

-1 -1 -1 1

62-66줄에서 탐색도중에 map이 -1인곳을 건드리면 visited를 -1로 바꿔주는데,

-1로 둘러싸인 부분은 아예 탐색이 접근하지를 않으므로 -1인데도 visited값이 0인 상태에 있게 되서 토마토가 모두 익지 않았다고 판별하네요

gongbea 6년 전 0

와.. 감사합니다 ㅠㅠ 진짜 예상못한부분에 문제가 있었네요 처음 입력받을때 -1이면 visited[][]에 -1을 입력하는 방법으로 수정했습니다. ㅠ

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

문제

문제

출처

ICPC

으아... ㅠ 질문게시판 테스트케이스는 거의다 돌려봤는데ㅠㅠ

gongbea 6년 전 0

3587jjh 6년 전 1

gongbea 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말