[Java Algorithm] ABCDE BOJ #13023

문제

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

13023번: ABCDE

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_13023 {

	static int n, m, parents[];
	static boolean result = false;
	static List<Integer>[] graph;
	static boolean[] visited;

	public static void dfs(int start, int cnt, boolean[] visited) {
		if(cnt == 5)  {
			result = true;
			return;
		}

		visited[start] = true;
		for(int i = 0; i < graph[start].size(); i++) {
			int now = graph[start].get(i);
			if(!visited[now]) {
				visited[now] = true;
				dfs(now, cnt+1, visited);
				visited[now] = false;
			}
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

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

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

		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a].add(b);
			graph[b].add(a);
		}

		for(int i = 0; i < n; i++) {
			dfs(i, 1, visited = new boolean[n]);
			if(result) {
				System.out.println(1);
				return;
			}
		}

		System.out.println(0);
	}
}

👉 DFS 문제

• graph라는 이름의 인접리스트를 만들어주었고, a -> b, b -> a 두 방향 모두 표현했다.
• 0부터 n-1까지의 모든 점을 시작점으로 하여서 dfs 메서드를 통해 가능한 경우들을 확인했다.
• dfs 메서드에서는 graph를 기반으로 이어진 점들로의 탐색을 진행했는데,
  탐색하려는 점의 visited가 false라면 이을 수 있도록 하였고, cnt로 이어진 점의 개수를 누적했다.
  cnt가 5가 되었다면 하나의 친구 관계를 찾은 것이므로 result를 true로 바꾼 후 리턴했다.

 

✔️ 반례 추천

[반례 1]
12 10
0 1
0 2
0 3
0 4
0 5
6 7
7 8
8 9
9 10
10 11

[반례 2]
5 4
0 1
1 2
2 3
3 0

 

💡 피드백

• 꼭 A->B->C->D->E 의 관계를 성립해야 하고,
  A->B, A->C->D->E 와 같은 관계는 맞지 않다는 것..!!만 생각하면 쉽게 풀 수 있는 문제였다.