[백준_13023번] ABCDE

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

13023번: ABCDE

[문제]

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

 

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

 

[입력 조건]

• 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
• 둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

 

[코드]

import java.util.*;

public class BaekJoon_13023 {
	static int n,m,result=0;
	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph=new ArrayList<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		visited=new boolean[n];
		
		for(int i=0;i<n;i++)
			graph.add(new ArrayList<>());
		
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			// 양방향
			graph.get(a).add(b); 
			graph.get(b).add(a);
		}
		
		for(int i=0;i<n;i++) {
			if(result==0) 
				find_friend(1,i); // i번째 노드와 연결된 노드 찾기
		}
		
		System.out.println(result);
	}
	
	static void find_friend(int depth, int start) {
		if(depth==5) { // 5개 이상 이어진 노드를 찾아야하기 때문에 깊이는 5까지 검사
			result=1; 
			return;
		}
		
		visited[start]=true; // 방문처리
		// start 노드와 연결된 모든 노드 탐색
		for(int i=0;i<graph.get(start).size();i++) {
			int next=graph.get(start).get(i); // 다음 노드
			
			if(!visited[next])
				find_friend(depth+1,next); // 방문하지 않았다면 다음 노드를 시작으로 연결된 노드 탐색
		}
		visited[start]=false; // 초기화
	}
}

 

[고찰]

 이번 문제는 문제를 잘못 이해해서 시간이 좀 걸렸던 문제였다. 처음에는 그래프의 사이클을 찾는 문제라고 판단해 union-find 방법을 사용해서 풀었지만 오답이었다.

 이번 문제는 사이클을 찾는 문제가 아니라 5개 이상 이어진 노드의 집합을 찾는 문제였다. 이를 구현하는 것은 어렵지 않았지만 문제를 읽고 무엇을 구해야하는지 이해하는데 어려움을 느꼈던 문제였다.