글 읽기 - 어디서 틀렸는지 감이 잡히질 않습니다.

doom233 6년 전 0

DFS로 모든 맵을 돌면서 섬 마다 라벨링을 해준 뒤,

각 섬의 가장자리 좌표를 벡터에 삽입한 뒤,

서로 다른 섬 끼리 거리를 측정했을 때, 가장 짧은 길이를 반환하도록 코딩하였습니다.

그러나 12%까지만 되고 바로 틀렸다고 뜨는데 아무리봐도 잘 모르겠어서 도움 요청드립니다..

import java.util.Scanner;
import java.util.Vector;
import java.awt.Point;


public class Main {
	
	private static int N;
	private static int Map[][];
	private static boolean visited[][];
	private static int xx[] = {-1,1,0,0};
	private static int yy[] = {0,0,-1,1};
	private static Vector<Point> v = new Vector<>();
	private static Vector<Integer> Land = new Vector<>();
	private static int land_num;
	
	public static void dfs(int x,int y) {
		if(visited[x][y]) return;
		visited[x][y]=true;
		
		for(int i=0;i<4;i++) {
			int nx = x+xx[i];
			int ny = y+yy[i];
			if(nx<0 || ny<0 || nx>N-1 || ny>N-1) continue;
			if(Map[nx][ny]==1) dfs(nx,ny);	// 다음 위치가 육지라면, dfs로 돌아준다.
			else if(Map[nx][ny]==0 && !v.contains(new Point(x,y))) {	// 인접 부분에 바다가 있다면,
				v.add(new Point(x,y));	// v에 해당 좌표를 넣어주고,
				Land.add(land_num);	// 라벨링을 해준다.
			}
		}
	}
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		Map = new int[N][N];
		visited = new boolean[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(!visited[i][j] && Map[i][j]==1) {	// 방문하지 않은 육지인 경우
					++land_num;	// 섬의 번호를 늘려주고, dfs로 돌면서 라벨링 및 바다에 근접한 육지를 찾아준다.
					dfs(i,j);		
				}
			}
		}
		if(land_num==1) {
			System.out.println("0");	// 섬이 하나 밖에 없다면, 0을 출력한다.
			return;
		}
		int min = 10000;
		
		for(int i=0;i<v.size();i++) {
			for(int j=i+1;j<v.size();j++) {
				if(Land.get(i)==Land.get(j)) continue;
				else {
					int distance = Math.abs(v.get(i).x - v.get(j).x)+Math.abs(v.get(i).y - v.get(j).y) - 1;
					//System.out.printf("land (from : %d,to : %d), distance : %d\n", Land.get(i),Land.get(j),distance);
					if(min>distance) min = distance;
				}
			}
		}
		System.out.println(min);
	}
}

ljh9032a 6년 전 1

가장자리라고 섬 사이의 가장 짧은 길이가 나오는게 아니네요

한 예로는 섬과 섬사이에 다른섬이 있다면 우회해서 가야겠죠..

doom233 6년 전 0

답변 감사합니다. 궁금한게 있는데, 섬과 섬 사이에 다른 섬이 있으면, 그 섬과 이으면 다리 길이가 최소가 되는거 아닌가요?? ㅠㅠ 제가 문제를 잘못 이해한건가요...

ljh9032a 6년 전 1

60 : if(Land.get(i)==Land.get(j)) continue;

이 부분이 이해가 안가네요... 라벨링을 해줄거면

28 : Land.add(land_num); // 라벨링을 해준다. 부분에서 이 벡터에 1, 1, 1, 2, 2, 2, 3, 3, ..이런 식으로 들어가는데

60줄과 의미가 이상한듯 하네요.. 아마 라벨링 2차원 배열을 생성 해서 표시 해야될 것 같아요

doom233 6년 전 0

ljh9032a / 아 그 부분 설명이 부족했군요 죄송합니다...

설명 드리면, DFS로 섬을 돌면서 가장자리를 뽑아내는데, 가장자리마다 라벨링을 해주는 방식입니다.

쉽게 말해서, 1번섬의 가장자리는 1번으로 라벨링, 2번 섬의 가장자리는 2번으로 라벨링 하는 방식입니다.

60줄의 의미는 같은 섬의 가장자리 간의 거리는 구하지 않는다는 의미입니다!

읽어주셔서 감사해요!!

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

문제

문제

출처

ICPC

어디서 틀렸는지 감이 잡히질 않습니다.

doom233 6년 전 0

ljh9032a 6년 전 1

doom233 6년 전 0

ljh9032a 6년 전 1

doom233 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말