[백준] 19542 전단지돌리기

 

1. 문제

2. 접근 방법

처음엔 단순히 DFS로 풀면 되겠다 생각하고 접근 하였는데

위 그림에서 1 - 2 - 4 와 1 - 2 - 3 - 5 - 6 두 방향을 이동할 때 1 - 2는 한번만 왔다 갔다 하면 되기 때문에

이동거리에서 중복 되는 부분의 처리가 필요했다.

 

중복처리를 어떻게 할까 고민하다 출발점에서 출발하여 중복처리를 하는 것보다

끝점에서 출발해서 출발점 까지 이동하며 visit 처리를 하면 훨씬 간단하게 중복을 처리 할 수 있을 것 같았다.

 

 

 

해당 방법을 사용하기 위해 우선 입력이 간선배열 형태이므로 출발점을 루프노드로 하는 트리로 변경해야 했다.

트리로 만들기 위해 모든 노드를 부모 자식으로 연결 시키고 그 중 자식이 하나도 없는 노드는 리프노드가 되므로 리프노드들도 알아낼 수 있다.

이제 모든 리프 노드로부터 탐색 하기만 하면 끝~

 

3. 풀이

1. 간선배열 형태의 입력을 인접 리스트로 받아오기

2. 인접 리스트에서 시작점부터 bfs로 자신의 부모를 제외한 연결된 모든 노드를 자식으로 두기

3. 자식이 하나도 없는 노드는 리프노드이므로 리프노드들만 따로 저장

4. 모든 리프노드에서 리프노드부터 자신의 부모를 계속 찾아가며 

 1) 루프노드를 만나거나

 2) 이미 방문한곳을 만나면 이동거리 return

5. 이동거리에서 힘만큼은 안가도 되고 왕복이므로 (거리 - 힘) * 2 를 result에 계속 더해서 저장.

//(거리-힘)이 음수일 경우 0으로 처리

6. result 출력

 

 

4. 자바코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P19542전단지돌리기 {

	static boolean visited[];
	static ArrayList<Integer> list[];
	static int cnt, D, parents[];

	static int find(int x) {
		if (parents[x] == x) //루프 노드를 만나면 지금까지 세어논 길이 return
			return cnt;
		if (visited[x]) { // 방문 했던 노드를 만나면 지금까지 세어논 길이 return 
			return cnt - 1;
		}
		cnt++;
		if (D < cnt) //힘이 거리보다 크면 방문을 하지 않으니 거리가 힘보다 클때만 방문처리 
			visited[x] = true;
		return find(parents[x]);

	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		D = Integer.parseInt(st.nextToken());
		list = new ArrayList[N + 1];
		for (int i = 0; i < N + 1; i++)
			list[i] = new ArrayList<Integer>();
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			list[x].add(y);
			list[y].add(x);
		}

		visited = new boolean[N + 1];
		ArrayList<Integer> leaflist = new ArrayList<Integer>();
		parents = new int[N + 1];
		for (int i = 1; i <= N; i++)
			parents[i] = i;
		Queue<Integer> que = new LinkedList<Integer>();
		que.add(S);
		while (!que.isEmpty()) { //bfs로 각 노드들의 부모 자식연결 (트리 생성)
			int now = que.poll();
			boolean isleaf = true;
			for (int i = 0; i < list[now].size(); i++) {
				if (parents[now] != list[now].get(i)) {
					isleaf = false;	
					que.add(list[now].get(i));
					parents[list[now].get(i)] = now;
				}
			}
			if (isleaf) //자식이 하나도 없다면 리프노드
				leaflist.add(now);
		}
		int result = 0;
		for (int leaf : leaflist) {
			cnt = 0;
			find(leaf);
			if (cnt - D > 0)
				result += (cnt - D) * 2; //세어논 거리에서 힘만큼 빼고 왕복이니 2배
		}
		System.out.println(result);
	}
}

5. 마치며

처음에 DFS로 어떻게든 풀어보려고 고민을 많이 했는데

그래프를 트리형태로 바꾸어 생각하니 간단하게 해결되었다...(문제 자체에 트리라 적혀 있긴한데..)

 

DFS로 현재노드가 리프노드로부터 얼마나 떨어져있는지 구해서 푸는 방법도 있던데

그 방법으로도 풀게되면 다시 리뷰해봐야겠다.

 

 

 

https://www.acmicpc.net/problem/19542

19542번: 전단지 돌리기