글 읽기 - 100%에서 틀리는데 반례좀..

sksdong1 7년 전 0

알고리즘은

1. 같은 육지끼리 섬 번호를 지정한다.

2. 바다로 확장해 나갈 수 있는 육지 정점들을 큐에 넣고 모든 정점에서 한칸씩 확장해 나간다.

3. 최초로 서로 다른 육지끼리 만난 경우 그 때까지의 경로의 합을 출력.

뭐가 문제일까요??

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main{

	int n,map[][],confirm[][],cnt;
	boolean chk[][];
	int dx[]={-1,1,0,0};
	int dy[]={0,0,-1,1};
	Queue<Point> queue = new LinkedList<Point>();

	Scanner sc = new Scanner(System.in);

	void solve(){
		n = sc.nextInt();
		map = new int[n][n];
		chk = new boolean[n][n];
		confirm = new int[n][n];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				map[i][j] = sc.nextInt();
			}
		}

		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(map[i][j]==1 && !chk[i][j]){ //같은 육지끼리 번호를 지정한다.
					++cnt;
					BFS(i,j);
				}
			}
		}

		//육지 중에서 상하좌우 중 한 변이라도 바다가 있으면 queue에 넣는다. 
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(map[i][j]==0) continue;
				boolean flag = false;
				for(int k=0;k<4;k++){
					int nx = i + dx[k];
					int ny = j + dy[k];
					if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
					if(map[nx][ny]==0) flag = true;
				}
				if(flag) queue.add(new Point(i,j,0));
			}
		}
		int ret = 0;
		
		while(!queue.isEmpty()){
			boolean flag = false;
			Point here = queue.poll();
			int x = here.x;
			int y = here.y;
			int w = here.w;
			for(int i=0;i<4;i++){
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
				if(map[nx][ny]!=0 && map[nx][ny]!=map[x][y]){ //다른 섬의 육지끼리 만남. -> 최소 길이 종료
					ret = confirm[nx][ny]+confirm[x][y];
					flag = true;
					break;
				}
				if(map[nx][ny]!=0) continue;
				map[nx][ny] = map[x][y];
				confirm[nx][ny]=w+1; //nx,ny위치의 다리가 얼마의 길이가 확장된 것인지 저장
				queue.add(new Point(nx,ny,w+1));
			}
			if(flag) break;
		}
		System.out.println(ret);


	}
	void BFS(int x,int y){
		//같은 육지끼리 번호를 지정
		LinkedList<Point> q = new LinkedList<Point>();
		q.add(new Point(x,y,0));
		chk[x][y] = true;
		map[x][y] = cnt;
		while(!q.isEmpty()){
			Point here = q.poll();
			x = here.x;
			y = here.y;

			for(int i=0;i<4;i++){
				int nx = x + dx[i];
				int ny = y + dy[i];
				if(nx<0 || ny<0 || nx>=n || ny>=n || map[nx][ny]==0) continue;
				if(!chk[nx][ny]){
					chk[nx][ny] = true;
					q.add(new Point(nx,ny,0));
					map[nx][ny] = cnt;
				}
			}
		}
	}
	public static void main(String[] args) {
		new Main().solve();
	}
}

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

blurabbity 7년 전 0

각각의 섬들에서 잇는 다리가 만나는 순간에 큐의 특성을 생각하면서 시뮬레이션해보면 그 알고리즘에 수정할 부분이 보일꺼에요.

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

문제

문제

출처

ICPC

100%에서 틀리는데 반례좀..

sksdong1 7년 전 0

blurabbity 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말