글 읽기 - 고수님들 도움 부탁드립니다.

toto 6년 전 0

안녕하세여.

홀로 알고리즘 공부하는 학생입니다.

테스트 케이스 모두 맞고, 여러 테스트케이스 해봐도 틀리는게 없는데,

37%에서 틀리는 이유를 모르겠네요..

바쁘시겠지만 반례나 틀린부분 확인 가능하다면 피드백 부탁드립니다.

감사합니다.

import java.awt.Point;
import java.util.*;

public class Test {  
	static int N;
	static int M;
	static int[][] MAP = new int[11][11];
	static int MAX =0;
	// 바이러스 위치
	static Point[] virus = new Point[11];
	// 바이러스 갯수
	static int VirusPointNum=0;
	
	// 방향
	static Point[] pos = new Point[4];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		pos[0] = new Point(0,1); // →
		pos[1] = new Point(1,0); // ↓
		pos[2] = new Point(0,-1); // ←
		pos[3] = new Point(-1,0); // ↑
		
		int wallCount=0;

		int[][] tempMAP = new int[11][11];

		for(int i=1; i<=N; i++) {
			for(int j=1; j<=M; j++) {
				MAP[i][j] = sc.nextInt();
				tempMAP[i][j] = MAP[i][j];
				if(MAP[i][j] == 2) {
					virus[VirusPointNum] = new Point(i,j);
					VirusPointNum++;
				}
			}
		}
		
		// 3개의 벽(1) 모든 경우의 수 두기
		for(int i=1; i<=N; i++){
			for(int j=1; j<=M; j++){
				wallMark(tempMAP, i,j, wallCount);
			}
		}
		
	System.out.println(MAX);
	}
				
	static void wallMark(int[][] temp, int i, int j, int wallCount) {
		
		int[][] tempMAP = new int[11][11];
		
		for(int x=1; x<=N; x++) {
			for(int y=1; y<=M; y++)
				tempMAP[x][y] = temp[x][y];
		}
		
		int zeroCount = 0;
		
		// 벽 3개 세웠으면
		if(wallCount == 3) {
			// 바이러스 퍼트려(2) 안전지대(0) 확인
			zeroCount = safeZoneCount(tempMAP);
			//System.out.println(zeroCount);
			if(zeroCount > MAX)
				MAX = zeroCount;
			return;
		}
		
		if(i>N)
			return;
		
		
		//벽 모든 경우의 수 놓기
		for(; i<=N; i++){
			if(j==M+1)
				j=1;
			for(; j<=M; j++) {
				if (tempMAP[i][j] == 0){
					tempMAP[i][j] = 1;
					wallCount++;
					
					if(j==M){
						if(i+1>N)
							return;
						wallMark(tempMAP, i+1, 1, wallCount);
						wallCount--;
						tempMAP[i][j] = 0;
					}
					else {
						wallMark(tempMAP, i, j+1, wallCount);
						wallCount--;
						tempMAP[i][j] = 0;
					}
				}
			}
		}
	}
	
	static int safeZoneCount(int [][] map) {
		int zeroCount = 0;
		
		// 바이러스 퍼뜨리기
		for(int i=0; i< VirusPointNum; i++)
			dfs(map, virus[i]);
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=M; j++) {
				if(map[i][j] == 0)
					zeroCount++;
			}
		}
		
		return zeroCount++;
		
	}
	
    //바이러스 퍼뜨리기
	static void dfs(int[][] map , Point p) {
		
		Point[] move = new Point[4];
		
		move[0] = new Point(p.x+pos[0].x, p.y + pos[0].y);
		move[1] = new Point(p.x+pos[1].x, p.y + pos[1].y);
		move[2] = new Point(p.x+pos[2].x, p.y + pos[2].y);
		move[3] = new Point(p.x+pos[3].x, p.y + pos[3].y);
		
		if(move[0].x <= N && move[0].x >= 1 && move[0].y <= M && move[0].y >=1) {
			if(map[move[0].x][move[0].y]==0) {
				map[move[0].x][move[0].y] = 2;
				dfs(map,move[0]);
			}
		}
		if(move[1].x <= N && move[1].x >= 1 && move[1].y <= M && move[1].y >=1) {
			if(map[move[1].x][move[1].y]==0) {
				map[move[1].x][move[1].y] = 2;
				dfs(map,move[1]);
			}
		}
		if(move[2].x <= N && move[2].x >= 1 && move[2].y <= M && move[2].y >=1) {
			if(map[move[2].x][move[2].y]==0) {
				map[move[2].x][move[2].y] = 2;
				dfs(map,move[2]);
			}
		}
		if(move[3].x <= N && move[3].x >= 1 && move[3].y <= M && move[3].y >=1) {
			if(map[move[3].x][move[3].y]==0) {
				map[move[3].x][move[3].y] = 2;
				dfs(map,move[3]);
			}
		}
	}
}

lowblow91 6년 전 3

반례 하나 찾아 드리자면

4 4
0 0 0 1
0 0 0 2
0 0 0 2
0 0 0 0

10이 되어야하는데 9가 나오네요

4 4
0 0 0 1
0 0 1 2
0 0 1 2
0 0 0 1

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

문제

문제

출처

ICPC

고수님들 도움 부탁드립니다.

toto 6년 전 0

lowblow91 6년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말