글 읽기 - [JAVA] 반례 도움 부탁드립니다.

janetasy 2년 전 0

반례 도움 부탁드립니다.
틀린 부분을 못 찾고 있는데요.
고수님들 도움 부탁드립니다.
import java.util.*;

public class Main {
	public static int N;
	public static int M;
	public static int[][] map;
	public static boolean[][] visited;
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	public static LinkedList<Pos> q = new LinkedList<>();
	public static int years = 0;

	public static class Pos {
		int x,y;
		Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

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

		map = new int[M][N];
		visited = new boolean[M][N];

		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
        
        // 처음부터 빙산이 두 덩이 이상이거나 모두 녹은 경우
        if (check()) {
            System.out.println("0");
            return;
        }
        init(); // visited 배열 초기화

        // check() 는 현재 빙산이 두 덩이 이상인지 모두 녹은 상태인지 리턴 받는데 해당 리턴 값이 true 일때까지 진행
		while (true) {
			for (int i=0; i<M; i++) {
				for (int j=0; j<N; j++) {
					if (map[i][j] > 0) {
                        // 빙산은 동시에 녹기 때문에 모든 빙산을 찾아 Q 에 넣어줌
						q.add(new Pos(i,j));
					}
				}
			}
			bfs(); // 빙산 녹는 것을 진행
			years++; // 빙산 녹는 것을 진행할 때마다 연수 추가
			init();
			if (check()) { // 현재 빙산이 두 덩이 이상인지 모두 녹은 상태인지 확인하여 계속 진행할지 그만 진행할 지 결정
				break;
			}
			init();
		}

		System.out.println(years); // 최종 걸린 연수 출력
	}

	public static void init() {
		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				visited[i][j] = false;
			}
		}
	}

	public static void bfs() {
		while (!q.isEmpty()) {
			Pos poll = q.poll();
			int curX = poll.x;
			int curY = poll.y;
			visited[curX][curY] = true;

			int cnt = 0;  // 위,아래,좌,우 중 바다(0)와 맡닿고 있는 면의 개수 카운트
			// 위, 아래, 좌, 우 확인
            for (int i=0; i<4; i++) {
				int nx = curX + dx[i];
				int ny = curY + dy[i];

				if (nx>=0 && ny>=0 && nx<M && ny<N) {
					if (map[nx][ny] == 0 && !visited[nx][ny]) {
						cnt++;
					}
				}
			}
            // 1년 후 녹은 빙산의 높이값 저장
			map[curX][curY] = map[curX][curY] - cnt;
			if (map[curX][curY] < 0) {
				map[curX][curY] = 0; // 0 이하일 경우는 바다(0) 로 처리
			}
			
		}
	}

	public static boolean check() {
		int num = 0;
		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j] > 0 && !visited[i][j]) {
                    // 빙산을 큐에 넣고 연결된 빙산 단위로 방문
					bfs_check(i,j);
					num++; // 빙산 덩어리의 개수
				}
			}
		}
		if (num > 1) { // 빙산 덩어리의 개수가 2개 이상이면 멈춤
			return true;
		}
		
        // 빙산 덩어리의 개수가 없으면 멈춤
		int cnt = 0;
		for (int i=0; i<M; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j] > 0) {
					cnt++;
				}
			}
		}
		if (cnt == 0) {
            return true;
        }
        
        // 그렇지 않으면 계속 진행
		return false;
	}

    // 빙산 덩어리 단위로 방문하여 빙산 덩어리의 개수 체크
	public static void bfs_check(int x, int y) {
		LinkedList<Pos> q = new LinkedList<>();
		q.add(new Pos(x, y));
		visited[x][y] = true;

		while (!q.isEmpty()) {
			Pos poll = q.poll();
			int curX = poll.x;
			int curY = poll.y;

			for (int i=0; i<4; i++) {
				int nx = curX + dx[i];
				int ny = curY + dy[i];

				if (nx>=0 && ny >=0 && nx<M && ny<N) {
					if (!visited[nx][ny] && map[nx][ny] != 0) {
						q.add(new Pos(nx,ny));
						visited[nx][ny] = true;
					}
				}
			}
		}
	}
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

[JAVA] 반례 도움 부탁드립니다.

janetasy 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
