[ALGO#8] 백준_15900_실버1_나무 탈출 : DFS [JAVA]

문제 링크

15900번: 나무 탈출

트리 특성을 이해하고 있는지 물어보는 그래프 탐색 문제 입니다.

DFS 핵심 문제 중 하나이고 트리의 성질까지 활용할 수 있는 좋은 문제였습니다.

한칸씩 앞으로 전진밖에 못하는 규칙때문에 어떤 게임말을 움직이는 것이 중요한 것이 아닌 누가 먼저하는지가 중요했습니다. 간선의 총합을 일자 직선으로 나타낼 수 있어 결국 긴 직선에서의 턴제였습니다. 

리프노드의 깊이가 간선 개수랑 같았습니다. 다시 말하면, 리프노드 깊이의 총 합 = 모든 노드의 간선의 개수

게임말이 이동할 수 있는 횟수에 따라 승패가 갈리게 됩니다. 

다른 문제에도 적용하기 위해 문제 회고를 해보겠습니다.

 

 

 

인접리스트(Adjacency List)

이 문제의 트리 탐색을 하려면 인접리스트를 알고 있어야 합니다.

트리를 표현하는 방법은 크게 2가지입니다. 인접행렬과 인접 리스트입니다.

이 문제는 입력 값이 커서 인접행렬로 풀면 시간 초과가 뜹니다.

그래서 인접리스트로 트리 탐색을 풀었습니다.

https://devlog-wjdrbs96.tistory.com/49

그래프(graph)의 구현 2가지

 

시간복잡도

이 문제는 시간 제한이 2초인데 입력값이  N(2 ≤ N ≤ 500,000) 입니다.

트리를 인접행렬로 만들어서 탐색할 때 (500,000 x 500,000) O(N^2)이 나와 시간 초과가 뜹니다.

그래서 인접리스트의 자료구조로 풀었습니다. 인접리스트 자료구조O(N+M)

 

Visited 배열 안 쓰고도 해결할 수 있구나

사실 둘 다 같은 방법인데 다른 관점으로 접근했습니다.

 

 

visited 배열 쓴 경우 : 방문한 노드가 아닐경우 탐색

public static void DFS(int node, int cnt, boolean[] visited) {
		visited[node] = true;

		for (int next : a.get(node)) {
			if (!visited[next]) {
				DFS(next, cnt + 1, visited);
			}
		}

		// 특정 노드가 루트 노드가 아니고, 노드의 인접리스트의 사이즈가 1이면
		// 그 노드는 리프 노드임.
		if (node != 1 && a.get(node).size() == 1) {
			ans += cnt;
		}
	}

 

visited 배열 안 쓴 경우 : 부모 노드의 번호를 매개변수로 넘겨줘서 그 번호를 제외한 다른 번호의 노드들만 dfs 탐색

private static void dfs(int cur, int p, int cnt) {  // 현재 노드, 부모 노드, 리프노드의 깊이
		
		for(int next : list[cur]) { // 헤드 노드의 요소들 
			if(next != p) { // 연결되 노드가 부모 노드가 아니라면
				dfs(next, cur, cnt+1);
			}
		}
		// 특정 노드가 루트 노드가 아니고, 노드의 인접리스트의 사이즈가 1이면
		// 그 노드는 리프 노드임.
		// 2. 인접 리스트는 실제로 연결된 노드들에 대한 정보만 저장하기 때문에, 그래프의 간선의 개수와 리스트 원소의 개수가 같다
		if(cur !=1 && list[cur].size()==1) { //리프 노드라면 깊이 추가
			answer+=cnt;
		}
	}

 

 

출력 구문

보통 if , else 나 변수의 삼항연산자로 표현하는데 한번에 코드를작성해봤습니다.
System.out.println((answer%2==0) ? "No" : "Yes"); // 간선의 총 합이 짝수면 짐, 홀수면 이김

 

 

출력 형태

문제를 정확히 푼 거 같은데 계속 틀렸다고 떠서 출력구문을 확인해보니 대소문자를 잘못 작성했습니다.

가벼운 실수지만 늦게 발견했습니다.

YES yes NO no  문제 출력 정확히 파악하자

 

 

예외 처리

사이즈가 1인 리스트가 반드시 루프노드가 아니라 루트 노드는 제외시켜야합니다.

백준 저 문제가 테케가 적은건지 cur !=1 조건을 제외시켜도 문제가 맞았다고 채점되네요.

+) 생각해보니 루트노드는 깊이가 0으로 설정해서 answer에 이미 0을 더해주고 있었네요. 

if(cur !=1 && list[cur].size()==1) { //리프 노드라면 깊이 추가
			answer+=cnt;
		}

 

DFS

DFS 탐색 할 때 (탐색 할) 다음 노드, (현재 노드, 부모)노드 번호, count로 매개변수를 만들었습니다.

 

 

성능 요약 : 메모리: 192604 KB, 시간: 828 ms

분류 : 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 트리(trees)

 

 

전체 코드 (JAVA)

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

// 그래프와 인접 리스트(adlist)
public class LinkedList_TEST {
	static LinkedList <Integer>[] list;
	static int answer;
	public static void main(String[] args) throws IOException {
		 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		// 인접 리스트 head 만들기, 0번 인덱스 헤드 비우고 루트 노드가 1번이기 때문에 N+1로 잡음
		list = new LinkedList[N+1];
		
		// N+1 자리에 결국 N번 노드가 들어가 (루트 노드가 1번부터 시작해 0번 인덱스 비워서 for문 1번 부터 )
		// 각 헤드마다인접 리스트 만들기
		for (int i = 1; i <= N; i++) {
			list[i] = new LinkedList<Integer>();
		}
		
		for (int i = 1; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()); // 연결된 노드 a
			int b = Integer.parseInt(st.nextToken()); // 연결된 노드 b
			
			//1.  ArrayList와 다른 점은 가용량(크기)이 의미가 없기 때문에 가용량을 받는 생성자가 존재하지 않는다는 점입니다.
			// 헤드 인덱스로 트리 구현 
			list[a].add(b); 
			list[b].add(a);
		}
		
		dfs(1, 0 ,0); // 1번 노드부터 시작, 부모노드, 간선의 개수 총합
		// 1은 루트 노드여서 부모가 없으니 0을 넣었다.
		
		System.out.println((answer%2==0) ? "No" : "Yes"); // 간선의 총 합이 짝수면 짐, 홀수면 이김
		br.close();
	}
	private static void dfs(int cur, int p, int cnt) {  // 현재 노드, 부모 노드, 리프노드의 깊이
		
		for(int next : list[cur]) { // 헤드 노드의 요소들 
			if(next != p) { // 연결되 노드가 부모 노드가 아니라면
				dfs(next, cur, cnt+1);
			}
		}
		// 특정 노드가 루트 노드가 아니고, 노드의 인접리스트의 사이즈가 1이면
		// 그 노드는 리프 노드임.
		// 2. 인접 리스트는 실제로 연결된 노드들에 대한 정보만 저장하기 때문에, 그래프의 간선의 개수와 리스트 원소의 개수가 같다
		if(cur !=1 && list[cur].size()==1) { //리프 노드라면 깊이 추가
			answer+=cnt;
		}
	}

}

 

혹시 잘못된 정보가 있다면 댓글 남겨주시면 감사드리겠습니다.