글 읽기 - [2573번 빙산]오답처리되는 원인이 무엇인지 모르겠습니다. 도움 부탁드립니다.

doo9012 6년 전 3

나름대로 여러 케이스를 확인했지만, 반례를 찾을 수 없었습니다.

도움 부탁드립니다.

테스트했던 케이스들입니다.

5 7
0 0 0 0 0 0 0
0 3 3 2 3 3 0
0 4 0 4 0 3 0
0 0 0 0 4 3 0
0 0 0 0 0 0 0
0

5 7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 10 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0

5 7
0 0 0 0 0 0 0
0 3 3 1 3 3 0
0 4 0 4 0 3 0
0 0 0 0 4 3 0
0 0 0 0 0 0 0
1

5 7
0 0 0 0 0 0 0
0 3 6 3 6 7 0
0 3 0 0 0 10 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
2

5 7
0 0 0 0 0 0 0
0 3 6 0 6 7 0
0 3 0 0 0 10 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0

5 7
0 0 0 0 0 0 0
0 9 8 9 8 9 0
0 9 8 9 8 9 0
0 9 8 9 8 9 0
0 0 0 0 0 0 0
0

5 7
0 0 0 0 0 0 0
0 9 8 3 8 9 0
0 9 8 0 8 9 0
0 9 8 9 8 9 0
0 0 0 0 0 0 0
5

5 5
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0

import java.util.*;

public class practice
{
	static int[][] map;
	static ArrayList<Pair> point = new ArrayList<Pair>();
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int n;
	static int m;
	
	static void dfs(int x, int y, boolean[][] chk)
	{
		for(int i=0; i<4; i++)
		{
			int r = x+dx[i];
			int c = y+dy[i];
			
			if(r<0 || r>=n
					|| c<0 || c>=m
					|| map[r][c]<=0
					|| chk[r][c])
			{
				continue;
			}
			
			chk[r][c] = true;
			dfs(r, c, chk);
		}
	}
	
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		map = new int[n+1][m+1];
		
		int i=0;
		int k=0;
		
		for(i=0; i<n; i++)
		{
			for(k=0; k<m; k++)
			{
				map[i][k] = sc.nextInt();
				if(map[i][k]==0) map[i][k]-=1; //물 부분을 -1로 처리
				else point.add(new Pair(i, k)); //빙산을 ArrayList에 입력
			}
		}
		
		int time=0;
		while(true)
		{
			int c=0;
			boolean[][] chk = new boolean[n+1][m+1];
			for(Pair p : point) //ArrayList안의 빙산 좌표로 DFS, 초기 입력 정보가 분리된 빙산일 수 있기 먼저 확인
			{
				if(!chk[p.x][p.y] && map[p.x][p.y]>0)
				{
					chk[p.x][p.y]=true;
					dfs(p.x, p.y, chk);
					c++;
				}
			}
			
			if(c>1) //2이상일 경우, 빙산이 분리된 것으로 판단하고 빠져나감
			{
				break;
			}
			
			time+=1;
			
			ArrayList<Pair> tmp = new ArrayList<Pair>();
			for(Pair p : point)//각 빙산의 동서남북에 물이 있는지 검사
			{
				int h=0;
				for(i=0; i<4; i++)
				{
					int x = p.x+dx[i];
					int y = p.y+dy[i];
					
					if(x<0 || x>=n
							|| y<0 || y>=m
							|| map[x][y] == 0)
					{
						continue;
					}
					
					if(map[x][y]<0)// 물일 경우(물 == -1)
						h++;
				}
				
				map[p.x][p.y]-=h; //map 정보 변경
				
				if(map[p.x][p.y]<0) //다음 포인트에 영향을 줄 수 있으므로 0보다 작을 경우, 0으로 변경
				{
					map[p.x][p.y]=0;
					tmp.add(p);
				}
			}
			
			for(Pair p : tmp) //0으로 변경된 물을 -1로 변경
			{
				map[p.x][p.y]-=1;
			}
			
			boolean b=true;
			for(Pair p : point)
			{
				if(map[p.x][p.y]>0) b=false; //빙산이 모두 녹았을 경우 확인
			}
			
			if(b)
			{
				time=0; //빙산이 모두 녹았을 경우, 0을 출력
				break;
			}
		}
		
		System.out.println(time);
	}
}

class Pair
{
	int x,y;
	Pair(int x, int y) 
	{
		this.x=x;
		this.y=y;
	}
}

wondy1128 6년 전 2

5 5
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 1 1 1 0

out: 2

인 경우

위 코드는 3 을 출력합니다.

doo9012 6년 전 1

감사합니다. 덕분에 해결되었습니다.

bllopi123 5년 전 3

위에 wondy1128님 테스트케이스는 잘못된거 아닌가요? 문제에 첫행 마지막행은 모두 0이라고 되어 있습니다.

wondy1128 5년 전 2

@bllopi123

그러네요 제가 문제를 제대로 안읽었네요. 죄송합니다.

7 7
0 0 0 0 0 0 0
0 1 1 0 1 1 0
0 1 9 1 9 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0

out : 2

위 코드는 3을 출력합니다.

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

문제

문제

출처

ICPC

[2573번 빙산]오답처리되는 원인이 무엇인지 모르겠습니다. 도움 부탁드립니다.

doo9012 6년 전 3

wondy1128 6년 전 2

doo9012 6년 전 1

bllopi123 5년 전 3

wondy1128 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말