[BOJ/Java] 13023. ABCDE

[BOJ/Java] 13023. ABCDE

13023번: ABCDE

---

문제 해석

이 문제는 친구 관계를 나타내는 그래프가 주어졌을 때, A-B-C-D-E와 같이 서로 친구인 5명이 연속으로 이어지는 관계를 찾는 문제다. 이는 그래프에서 길이가 4인 경로를 찾는 것과 동일하다.

풀이 과정

1. 각 사람의 친구 관계를 양방향 그래프로 표현하고, 인접 리스트로 구현한다.
2. 각 노드를 시작점으로 하여 깊이 우선 탐색(DFS)을 실행한다. 각 노드에서 시작할 때, 해당 노드를 방문한 것으로 표시한다.
3. DFS를 통해 깊이가 4가 되는 순간을 찾는다. 깊이가 4가 되면 5명이 연속으로 이어진 것이므로 답을 찾은 것이다.
4. 깊이가 4에 도달하면 결과를 저장하고 더 이상 탐색을 계속하지 않는다.
5. 모든 노드에 대해 탐색을 마친 후, 결과를 출력한다. 만약 5명이 연속으로 이어진 경우를 찾지 못하면 0을 출력한다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No13023;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		new Main().sol();
	}

	private int n;  // 사람의 수
	private int m;  // 친구 관계의 수
	private List<ArrayList<Integer>> graph;  // 인접 리스트로 그래프 표현
	private StringBuilder sb = new StringBuilder();  // 결과 저장용

	private void sol() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		graph = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			graph.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			graph.get(from).add(to);
			graph.get(to).add(from);  // 양방향 그래프로 친구 관계를 추가
		}

		
		for (int i = 0; i < graph.size(); i++) {
			boolean[] v = new boolean[n];
			v[i] = true;
			dfs(i, v, 0);  // 각 노드를 시작점으로 DFS 실행
			if (sb.length() != 0) break;
		}
		if (sb.length() == 0) sb.append(0);  // 5명이 연속으로 이어진 경우를 찾지 못한 경우
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private void dfs(int k, boolean[] v, int cnt) {
		if(sb.length() != 0) {  // 이미 답을 찾은 경우 더 이상 탐색하지 않음
			return;
		}
		
		if(cnt == 4) {  // 깊이가 4인 경우 (5명이 연속으로 이어진 경우)
			sb.append(1);
			return;
		}

		for (int j = 0; j < graph.get(k).size(); j++) {
			int cur = graph.get(k).get(j);
			if(!v[cur]) {
				v[cur] = true;
				dfs(cur, v, cnt+1);  // 깊이를 증가시키며 탐색
				v[cur] = false;  // 다른 경로 탐색을 위해 방문 해제
			}
		}
	}
}

시간 복잡도 분석

이 알고리즘은 DFS를 사용하여 각 노드에서 시작하여 깊이 4의 경로를 찾는다. 최악의 경우, 모든 노드에서 탐색을 수행해야 하므로 시간 복잡도는 O(n⋅m)이 될 수 있다, 여기서 n은 노드의 수, m은 각 노드에서 연결된 간선의 수를 나타낸다.

느낀점

이 문제는 그래프의 깊이 우선 탐색을 통해 특정 길이의 경로를 찾는 전형적인 문제다. DFS를 활용하여 깊이 기반의 탐색을 수행하는 방법을 잘 이해하고 있어야 효과적으로 문제를 해결할 수 있다.