[백준/자바] 13023번: ABCDE

문제

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

풀이

• 총 N명의 사람
  • 사람들은 0번부터 N-1번으로 번호가 매겨져 있다.
• 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구하려고 한다.
  • A는 B와 친구
  • B는 C와 친구
  • C는 D와 친구
  • D는 E와 친구
• 위 조건에 맞는 친구관계가 존재하면 1, 없으면 0 출력

여러 사람들이 주어졌을 때, 5명이 친구관계인 경우를 찾는 문제입니다.

즉, 노드와 노드의 연결 깊이가 5인 경우를 찾는 DFS문제입니다.

입력

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

• n: 사람 수
• m: 친구 관계 수

		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 a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

• graph: 친구 관계를 저장할 인접 리스트
• a, b: 친구 관계
  • 친구 관계는 양방향 관계이므로 양방향으로 저장하였습니다.

탐색

		visited = new boolean[n];
		answer = 0;
		for (int i = 0; i < n; i++) {
			dfs(1, i);
			if (answer == 1) break;
		}

• visited: 탐색한 사람 여부를 나타내는 배열
• answer: 정답
• dfs: 모든 노드에서 탐색을 시작할 DFS 메서드
  • 만약 결과가 1이면 탐색 종료

	private static void dfs(int depth, int cur) {
		if (depth == 5) {
			answer = 1;
			return;
		}
		
		visited[cur] = true;
		for (int nxt : graph.get(cur)) {
			if (!visited[nxt]) dfs(depth + 1, nxt);
			
			if (answer == 1) return;
		}
		visited[cur] = false;
	}

• depth, cur: 연결되어 있는 친구의 수(자신 포함), 현재 탐색 중인 사람
• 만약 5명이 친구임을 알았다면 결과를 1로 변환 후 리턴
• 아니라면 현재 사람 방문 처리
  • 현재 사람과 연결되어 있는 친구들 탐색
  • 연결되어 있는 사람 중 방문하지 않은 사람이라면 재귀
  • 탐색이 종료되었다면 방문 처리 해제(백트래킹)

출력

		System.out.println(answer);

• 탐색이 종료되었다면, 결과를 출력합니다.

코드

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

public class Main_13023 {
	static int n, m, answer;
	static boolean[] visited;
	static List<ArrayList<Integer>> graph;
	
	private static void dfs(int depth, int cur) {
		if (depth == 5) {
			answer = 1;
			return;
		}
		
		visited[cur] = true;
		for (int nxt : graph.get(cur)) {
			if (!visited[nxt]) dfs(depth + 1, nxt);
			
			if (answer == 1) return;
		}
		visited[cur] = false;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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 a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		
		visited = new boolean[n];
		answer = 0;
		for (int i = 0; i < n; i++) {
			dfs(1, i);
			if (answer == 1) break;
		}
		
		System.out.println(answer);
	}

}