[Baekjoon] 백준 13023 ABCDE (G5^ / DFS, 그래프) - Java

링크

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

13023번: ABCDE

 

 

 

문제 해석

A -> B -> C -> D -> E 관계를 가지는 친구가 있는지를 구하시오.

 

 

 

코드

package algo.bj.g5_13023;

import java.io.*;
import java.util.*;

public class Main {
	static ArrayList<Integer>[] list;
	static boolean[] v;
	static int answer;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken()); // 엣지 수
		
		// init
		list = new ArrayList[N];
		for (int i = 0; i < list.length; i++) {
			list[i] = new ArrayList<>();
		}
		
		// input
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			list[from].add(to);
			list[to].add(from);
		}
		answer = 0;
		for (int i = 0; i < N; i++) {
			if (answer == 1) {
				break;
			}
			v = new boolean[N];
			v[i] = true;
			dfs(i, 1);
		}
		System.out.println(answer);
	}
	
	private static void dfs(int now, int count) {
		if (count >= 5) {
			answer = 1;
			return;
		}
		for (Integer nextNode : list[now]) {
			if (v[nextNode] == false) {
				v[nextNode] = true;				
				dfs(nextNode, count+1);
				if (answer == 1) return;
				v[nextNode] = false;
			}
		}
	}
}

 

 

 

코드 해석

ABCDEFU

해당 문제는 예시로 든 친구 관계를 이해하는 것이 상당히 난해한 문제입니다.

 

위에서 제시한 관계는 연속적으로 5개의 노드가 이어지는 경우가 존재하는지를 물어보는 것입니다.

 

관계의 연속성을 물어 보는 것이므로 깊이 탐색, 즉 DFS를 활용하면 문제를 풀 수 있습니다.

 

 

 

 

발생한 문제 & 해결 방안

친구 관계가 순환관계면 안되는 것인지, 기준이 무엇인지를 잡는게 상당히 어려웠다.

 

결국 Solution을 보고 이해한 후 코드를 작성할 수 있었다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice