글 읽기 - 게시판의 모든 반례를 통과했지만, 10%에서 틀리네요..

syg4806 3년 전 0

1. dfs를 이용해 cctv가 볼수있는 모든 방향을 탐색합니다.

2. 각 뎁스에서 cctv가 볼 수 있는 곳을 myArea에 넣습니다.

3. cctv가 바라보는 곳의 중복이 있을 수 있기 때문에, UNWATCHED인 곳만 myArea에 넣습니다.

4. dfs가 리턴되어 돌아오면 myArea에 있는 좌표들을 UNWATECHED로 다시 변경합니다.

최종적으로 area가 가장 많이 보았을 때 - cctv개수 - 벽의 갯수 를 출력하게끔 구성했습니다...

무엇이 문제일까요,,, 반례를 찾아주시면 너무 감사하겠습니다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int N;
	static int M;
	static int[][] office;
	static ArrayList<CCTV> cctvList = new ArrayList<CCTV>();
	static int min = Integer.MAX_VALUE;
	static Pair UP = new Pair(-1, 0);
	static Pair RIGHT = new Pair(0, 1);
	static Pair DOWN = new Pair(-1, 0);
	static Pair LEFT = new Pair(0, -1);
	static Pair[][] cctvType = { null, { UP }, { LEFT, RIGHT }, { UP, RIGHT }, { LEFT, UP, RIGHT },
			{ UP, RIGHT, DOWN, LEFT } };
	static final int WALL = 6;
	static final int WATCHED = -1;
	static final int UNWATCHED = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		office = new int[N][M];
		int wallCount = 0;
		for (int row = 0; row < N; row++) {
			for (int col = 0; col < M; col++) {
				office[row][col] = sc.nextInt();
				if (office[row][col] == WALL) {
					wallCount++;
				} else if (office[row][col] != UNWATCHED) {
					cctvList.add(new CCTV(row, col, office[row][col]));
				}
			}
		}
		dfs(0, N * M);
		System.out.println(min - wallCount - cctvList.size());
	}

	private static void dfs(int index, int count) {
		if (index == cctvList.size()) {
			min = Math.min(count, min);
			return;
		}
		CCTV cctv = cctvList.get(index);
		for (int i = 0; i < 4; i++) {
			Pair<Integer, Integer>[] area = turn(cctvType[cctv.type], i);
			ArrayList<Pair<Integer, Integer>> myArea = watch(area, cctv);
			dfs(index + 1, count - myArea.size());
			unWatch(myArea);
		}
	}

	private static void unWatch(ArrayList<Pair<Integer, Integer>> myArea) {
		for (Pair<Integer, Integer> area : myArea) {
			office[area.row][area.col] = UNWATCHED;
		}
	}

	private static ArrayList<Pair<Integer, Integer>> watch(Pair[] area, CCTV cctv) {
		ArrayList<Pair<Integer, Integer>> watchingArea = new ArrayList();
		int row = cctv.row;
		int col = cctv.col;
		for (Pair<Integer, Integer> watchingWay : area) {
			for (int i = 1; i < 8; i++) {
				int watchRow = row + watchingWay.row * i;
				int watchCol = col + watchingWay.col * i;
				if (!isWatchable(watchRow, watchCol)) {
					break;
				}
				if (office[watchRow][watchCol] == WATCHED) {
					continue;
				} else if (office[watchRow][watchCol] == UNWATCHED) {
					office[watchRow][watchCol] = WATCHED;
					watchingArea.add(new Pair(watchRow, watchCol));
				}

			}
		}
		return watchingArea;
	}

	private static boolean isWatchable(int watchRow, int watchCol) {
		return watchRow >= 0 && watchRow < N && watchCol >= 0 && watchCol < M && office[watchRow][watchCol] != WALL;
	}

	private static Pair<Integer, Integer>[] turn(Pair[] area, int turnCount) {
		Pair[] newArea = new Pair[area.length];
		for (int index = 0; index < area.length; index++) {
			newArea[index] = getTurnArea(area[index], turnCount);
		}
		return newArea;
	}

	private static Pair<Integer, Integer> getTurnArea(Pair area, int turnCount) {
		Pair<Integer, Integer> newArea = new Pair(area.row, area.col);
		for (int i = 0; i < turnCount; i++) {
			int row = newArea.row;
			int col = newArea.col;
			if (col == 0) {
				newArea.row = col;
				newArea.col = -row;
			} else if (row == 0) {
				newArea.row = col;
				newArea.col = row;
			}
		}
		return newArea;
	}

	static class CCTV {
		int type;
		int row;
		int col;

		CCTV(int row, int col, int type) {
			this.type = type;
			this.row = row;
			this.col = col;
		}
	}

	static class Pair<L, R> {
		L row;
		R col;

		public Pair(L left, R right) {
			this.row = left;
			this.col = right;
		}

		static <L, R> Pair<L, R> of(L left, R right) {
			return new Pair<L, R>(left, right);
		}
	}

}

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

문제

문제

출처

ICPC

게시판의 모든 반례를 통과했지만, 10%에서 틀리네요..

syg4806 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말