글 읽기 - 이왜틀을 시전 중입니다. 반례가 있을까요?

ybc125 1년 전 1

테스트케이스 다 맞고 문제 없어보이는데 틀립니다 반례가 뭘까요

package 완전탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj_17144_미세먼지안녕 {
	static int N, M, airClear[][], map[][], delta[][] = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } }, clearedDust;

	public static void main(String[] args) throws IOException {

		// 1. 공기청정기 윗쪽, 아랫쪽 위치 좌표 파악
		// 2. 미세먼지 확산 (delta 4방향)
		// 3. 공기청정기 작동(위쪽은 반시계, 아랫쪽은 시계 방향 회전)
		// T초 지난 후 양수값 합 = answer

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		clearedDust = 0;
		N = Integer.parseInt(stz.nextToken());
		M = Integer.parseInt(stz.nextToken());
		int T = Integer.parseInt(stz.nextToken());
		map = new int[N][M];
		airClear = new int[2][2];

		int cnt = 0;
		for (int i = 0; i < N; i++) {
			stz = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(stz.nextToken());
				if (map[i][j] == -1 && cnt == 0) {
					airClear[0][0] = i;
					airClear[0][1] = j;
					cnt++;
				} else if (map[i][j] == -1 && cnt == 1) {
					airClear[1][0] = i;
					airClear[1][1] = j;
				}
			}
		}

		while (T-- > 0) { // T초 동안 진행
			spreadDust();
			clearDust();
		}

		int totalDust = 2; // 공기청정기 -2 고려
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				totalDust += map[i][j];
			}
		}
		System.out.print(totalDust);

	}

	private static void spreadDust() {
		int tempMap[][] = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] > 0) {
					int spreadCnt = 0;
					int spreadDustSize = map[i][j] / 5;
					for (int k = 0; k < delta.length; k++) {
						int nr = i + delta[k][0];
						int nc = j + delta[k][1];
						if (!check(nr, nc))
							continue;

						if (map[nr][nc] == -1)
							continue;

						tempMap[nr][nc] += spreadDustSize;
						spreadCnt++;
					}
					tempMap[i][j] -= spreadCnt * spreadDustSize;
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] += tempMap[i][j];
			}
		}
	}

	private static boolean check(int nr, int nc) {
		return 0 <= nr && nr < N && 0 <= nc && nc < M;
	}

	private static void clearDust() {
		int upperPartR = airClear[0][0];
		int upperPartC = airClear[0][1];
		int lowerPartR = airClear[1][0];
		int lowerPartC = airClear[1][1];

		for (int i = upperPartC; i - 1 >= 0; i--) {
			if (i == upperPartC) {
				continue;
			} else {
				map[i][0] = map[i - 1][0];
			}
		}

		for (int i = 0; i + 1 < M; i++) {
			map[0][i] = map[0][i + 1];
		}

		for (int i = 0; i + 1 <= upperPartR; i++) {
			map[i][M - 1] = map[i + 1][M - 1];
		}

		for (int i = M - 1; i - 1 >= 0; i--) {
			if (i - 1 == 0) {
				map[upperPartR][i] = 0;
			} else {
				map[upperPartR][i] = map[upperPartR][i - 1];
			}
		}

		// 아랫쪽 공기청정기
		for (int i = lowerPartR; i + 1 < N; i++) {
			if (i == lowerPartR) {
				continue;
			} else {
				map[i][0] = map[i + 1][0];
			}
		}

		for (int i = 0; i + 1 < M; i++) {
			map[N - 1][i] = map[N - 1][i + 1];
		}
		
		for (int i = N - 1; i > lowerPartC; i--) {
			map[i][M - 1] = map[i - 1][M - 1];
		}

		for (int i = M - 1; i > 0; i--) {
			if (i == 1) {
				map[lowerPartR][i] = 0;
			} else {
				map[lowerPartR][i] = map[lowerPartR][i - 1];
			}
		}
	}
}

dlbae9613 1년 전 5

공기청정기 처리 로직이 잘못되었습니다. 예외 케이스 하나 드립니다.

8 8 10
7 6 5 4 3 2 1 2
8 0 0 0 0 0 0 3
9 0 0 0 0 0 0 4
-1 7 8 9 8 7 6 5
-1 7 8 9 8 7 6 5
9 0 0 0 0 0 0 4
8 0 0 0 0 0 0 3
7 6 5 4 3 2 1 2


output : 138
answer : 130

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

문제

문제

출처

ICPC

이왜틀을 시전 중입니다. 반례가 있을까요?

ybc125 1년 전 1

dlbae9613 1년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말