글 읽기 - 잘못된 부분을 찾습니다

citizen 7년 전 0

일단 입력에서 주어진 두 정점 쌍(u, v)에서 v가 다른 부모정점의 자식이 아닌이상

u에게 먼저 부모정점이 될 우선권을 주어놓고 문제를 풀었습니다.

1번 정점이 항상 루트가 아닐 수 있기에 배열을 따로 만들어 자식으로서 한번도

등장해본 적 없는 정점의 번호가 루트의 번호라는 점을 이용하여 루트를 찾았구요.

DP를 이용해서 한 번 접근을 해봤습니다.

DP[N, IsAdapter] = N번 정점이 얼리어뎁터 일 경우/가 아닌 경우 필요한 얼리어뎁터의 갯수;

로 DP를 정의해봤는데요.

Solve함수에서 IsAdapter변수가 0이면 해당 정점은 얼리어뎁터가 아니며,

이 경우에는 자식노드는 모두 얼리어뎁터가 되야합니다.

반대로 IsAdapter변수 값이 1이면 해당 정점은 얼리어뎁터이며,

자식노드 IsAdapter값으로 1과 0 둘 중 하나를 가질 수 있습니다.

자식노드의 IsAdapter값이 무엇이냐에 따라서 DP값이 달라지기 때문에

둘 중 최소값인 골라 더해주기로 했습니다.

여러가지 예제를 스스로 만들어가보면서 시험해봤는데

문제가 될만한 TC를 아직 발견하지 못했습니다.

도움을 주셨으면 합니다.

import java.util.*;
import java.awt.List;
import java.io.*;
import java.math.*;
 
public class Main{
    public static BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = 
            new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static int n, E1, E2, min, Root;
    public static Friend[] friend;
    public static int[][] dp;
    
    public static void main(String args[]) throws IOException{
    	Scanner sc = new Scanner(System.in);
    	StringTokenizer st;
    	n = Integer.parseInt(br.readLine());
    	friend = new Friend[n+1];
    	for(int i = 1; i <= n; i++) friend[i] = new Friend();
    	dp = new int[n+1][2];
    	for(int i = 1; i <= n; i++) for(int j = 0; j < 2; j++) dp[i][j] = -1;
        int[] HasParent = new int[n+1];
        for(int i = 1; i < n; i++){
        	st = new StringTokenizer(br.readLine(), " ");
        	E1 = Integer.parseInt(st.nextToken());
        	E2 = Integer.parseInt(st.nextToken());
        	if(HasParent[E2] != -1){
        		HasParent[E2] = -1;
        		friend[E1].list.add(E2);
        		friend[E1].size++;
        	}else{
        		HasParent[E1] = -1;
        		friend[E2].list.add(E1);
        		friend[E2].size++;
        	}
        }
        Root = 0;
        for(int i = 1; i <= n; i++){
        	if(HasParent[i] != -1){
        		Root = i;
        		break;
        	}
        }
        bw.write(Math.min(solve(Root, 0), solve(Root, 1))+"");
    	bw.close();
    }
    
    public static int solve(int FN, int IsAdapter){
    	if(dp[FN][IsAdapter] == -1){
    		if(IsAdapter == 1){
    			dp[FN][IsAdapter] = 1;
    			for(int i = 0; i < friend[FN].size; i++){
    				int next = friend[FN].list.get(i);
    				dp[FN][IsAdapter] += Math.min(solve(next, 0),
    						solve(next, 1));
    			}
    		}else{
    			dp[FN][IsAdapter] = 0;
    			for(int i = 0; i < friend[FN].size; i++){
    				dp[FN][IsAdapter] += solve(friend[FN].list.get(i), 1);
    			}
    		}
    	}
    	return dp[FN][IsAdapter];
    }
    
    static class Friend{
    	int size;
    	ArrayList<Integer> list;
    	
    	public Friend(){
    		size = 0;
    		list = new ArrayList<Integer>();
    	}
    }
    
}

bupjae 7년 전 5

입력이 다음과 같이 들어왔을 때 트리가 제대로 생성이 안 되는것 같습니다. 확인해 보세요.

4

1 2

3 4

2 4

citizen 7년 전 0

문제점을 분석해본 결과

트리 정점의 번호가 오름차순으로 주어지지 않을 수도 있다는 점,

그리고 굳이 Root를 찾지 않아도 solve를 통해(visited 배열이 추가된다면)

저절로 트리 구조가 만들어지기 때문에 Root를 1로 생각해도 된다는 점을 놓치고 있었네요.

아직 제가 트리에 대한 개념이 좀 부족한것 같습니다..

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