백준 19542 <전단지 돌리기>

문제의 중점은 그래프를 이해하고 리프 노드에서부터 시작해서 거리가 D거리 이하인 부분은 제외한 뒤 왕복하는 거리를 구하는 문제다.

 

그래프를 나타내기 위해 우선적으로 각각의 노드가 연결된 노드를 넣어줄 ArrayList 배열을 만든 뒤 삽입했다.

 

이 부분을 이해하기 위해서는 백준의 2644번 촌수 계산 문제를 풀어보는 것이 도움이 된다!

www.acmicpc.net/problem/2644

2644번: 촌수계산

그 후 dfs를 이용해서 return 하는 값을 이용해 시작점까지 돌아오는 방법을 이용했다!

 

그래프를 이용함으로써 현재 위치에서 이전 위치로 돌아가지 않게 하는 방법이 필요했는데 이는 visit [] 배열을 이용해 처리했다.

 

시작 위치를 visit [s]=1 해줌으로써 시작을 나타냈다.

이 부분은 각각의 노드가 연결된 노드가 방문하지 않았으면 그 노드를 방문하고 다음 dfs로 가는 부분이다.

 

return 값은 갔다가 돌아온 거리와 전단지를 던질 수 있는 거리를 나타낼 수 있도록 Point형을 나타내 x좌표는 왕복거리,

y좌표는 리프노드에서 거리를 나타냈다.

리프 노드에 도달하게 되면 다음 방문할 노드가 없기 때문에 돌아가면서 던질 수 있는 거리를 확인하기 위해 Y값을 증가시킨다. 또한 그 범위가 d보다 작으면 x값을 0 그대로 리턴하게 된다.

6의 리프노드에서 return을 하게 되면 5의 p.y값은 1이 되고 d와 같기 때문에 왕복거리인 x를 2 증가시킨다.

그 후 2의 리프 노드와 5 노드에서 리턴한 값을 노드 4에서 계산을 해주게 되는데 그때 4 위치에서는 5의 거리까지 방문해줘야 하기 때문에 가장 긴 거리의 y값을 가지게 된다.

 

코드를 구성하면서 예외 처리를 해줘야 했던 부분

기존에는 이 부분을 처리하지 않고 dis.x+=2를 해줬었는데 그렇게 되면 처음 부분도 +2를 해주기 때문에  

이렇게 처리를 해주었다. 그렇게 함으로써 생긴 문제점은 총길이가 d보다 작다면 0에서 -2를 해주기 때문에 -2가 나오는 문제점이 있었다.

그 결과 4번의 틀렸습니다가 발생했다 ㅠㅠ

 

DFS로 문제를 풀어보았는데 다음에는 BFS 이용해 문제를 접근하는 방법을 생각해봐야겠다.

 

전체 코드

 

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	
	static int n,s,d,visit[];
	static ArrayList<Integer> a[];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(kb.readLine());
		n=Integer.parseInt(st.nextToken());
		s=Integer.parseInt(st.nextToken());
		d=Integer.parseInt(st.nextToken());
		a=new ArrayList[n+1];
		visit=new int[n+1];
		for(int i=1;i<=n;i++) {
			a[i]=new ArrayList<Integer>();
		}
		for(int i=1;i<n;i++) {
			st=new StringTokenizer(kb.readLine());
			int first=Integer.parseInt(st.nextToken());
			int second=Integer.parseInt(st.nextToken());
			a[first].add(second);
			a[second].add(first);
		}
		visit[s]=1;
		System.out.println(dfs(s).x);
		
		
	}
	public static Point dfs(int num) {
		Point dis=new Point(0,0);
		for(int i=0;i<a[num].size();i++) {
			if(visit[a[num].get(i)]==0) {
				visit[a[num].get(i)]=1;
				Point re=dfs(a[num].get(i));
				dis.x+=re.x;
				dis.y=Math.max(re.y, dis.y);
			}
		}
		if(dis.y<d) {
			return new Point(0,dis.y+1);
		}
		if(num!=s)
			dis.x+=2;
		dis.y++;
		return dis;
	}

}