[BaekJoon] 13023 ABCDE

1.  문제 링크

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

2.  문제

요약

• 캠프에 참가하는 N명에 대해 0번부터 N - 1번으로 번호가 매겨져 있고, 일부 사람들은 친구입니다.
• 아래와 같은 관계를 가진 사람 A,B,C,D,E가 존재하는지 판단하는 프로그램입니다.
  • A와 B는 친구다.
  • B와 C는 친구다.
  • C와 D는 친구다.
  • D와 E는 친구다.
• 입력: 첫 번째 줄에 5보다 크거나 같고 2,000보다 작거나 같은 사람의 수 N이 주어지고 1보다 크거나 같고 2,000보다 작거나 같은 친구 관계의 수 M이 주어집니다. 두 번째 줄부터 M개의 줄에는 0보다 크거나 같고 N - 1보다 작거나 같은 정수 a, b가 주어지고 a와 b는 같지 않으며 이 뜻은 a와 b가 친구라는 뜻입니다.
• 출력: 첫 번째 줄에 A,B,C,D,E가 존재하면 1을 출력하고 없으면 0을 출력합니다.

3.  소스코드

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.Arrays;

public class Main {
	boolean isRelation = false;
	public void findRelation(int start, ArrayList<ArrayList<Integer>> relations, boolean[] visited, int count) {
		if(count == 5) {
			isRelation = true;
			return;
		}
		visited[start] = true;
		for(int i : relations.get(start)) {
			if(!visited[i]) {
				findRelation(i, relations, visited, count + 1);
			}
			if(isRelation) {
				return;
			}
		}
		visited[start] = false;
	}
	
	public int getRelationNum(int people_num, ArrayList<ArrayList<Integer>> relations) {
		boolean[] visited = new boolean[people_num];
		for(int i = 0; i < people_num; i++) {
			Arrays.fill(visited, false);
			findRelation(i, relations, visited, 1);
			if(isRelation) {
				return 1;
			}
		}
		return 0;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int people_num = Integer.parseInt(input[0]);
		int relation_num = Integer.parseInt(input[1]);
		ArrayList<ArrayList<Integer>> relations = new ArrayList<ArrayList<Integer>>();
		for(int i = 0; i < people_num; i++) {
			relations.add(new ArrayList<Integer>());
		}
		for(int i = 0; i < relation_num; i++) {
			input = br.readLine().split(" ");
			relations.get(Integer.parseInt(input[0])).add(Integer.parseInt(input[1]));
			relations.get(Integer.parseInt(input[1])).add(Integer.parseInt(input[0]));
		}
		br.close();
		Main m = new Main();
		bw.write(m.getRelationNum(people_num, relations) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• 위 조건을 생각해보면 A와 B, B와 C, C와 D, D와 E가 친구여야하므로 각 참가자를 점으로 생각해본다면 0번부터 N - 1번까지의 점 중 일직선으로 연결된 점이 5개가 있는 것과 같은 의미입니다.
• 일직선으로 연결된 점이 5개가 있는지 확인할 때는 DFS를 이용하여 확인합니다.
• 한 번호부터 시작하여 해당 번호와 친구인 다른 번호들을 확인하고 친구인 각 번호들에 대해서도 각 번호와 친구인 다른 번호들을 확인하면서 방문할 수 있는 번호들을 모두 방문합니다.
• 방문한 번호는 다시 방문하지 않고 위 방법을 이용하여 방문할 수 있는 번호들을 방문해보며 방문한 번호의 개수가 5라면 일직선으로 연결된 점이 5개가 된 것이므로 문제의 조건에 맞는 A,B,C,D,E가 존재한다는 뜻이 되고 그렇지 않다면 해당 번호에서는 존재하지 않는다는 뜻이 됩니다.

public void findRelation(int start, ArrayList<ArrayList<Integer>> relations, boolean[] visited, int count) {
		if(count == 5) {
			isRelation = true;
			return;
		}
		visited[start] = true;
		for(int i : relations.get(start)) {
			if(!visited[i]) {
				findRelation(i, relations, visited, count + 1);
			}
			if(isRelation) {
				return;
			}
		}
		visited[start] = false;
	}

1. 각 번호에 대해 해당 번호의 친구들을 나타낼 변수 relations를 생성하고 입력에 관계들이 들어오면 relations 변수에 해당 관계를 설정합니다.
2. DFS를 통해 각 번호를 방문할 것인데 각 번호를 방문하였는지를 나타내는 1차원 배열 변수 visited를 생성합니다.
3. 모든 번호들을 돌면서 A,B,C,D,E 관계가 있는지 확인합니다.
   1. 아직 방문 전이기 때문에 visited 변수의 모든 값을 false로 설정합니다.
   2. DFS를 통해 A,B,C,D,E 관계가 해당 번호에서 존재하는지 확인합니다.
      1. 탐색하려는 번호를 방문하였으므로 해당 번호의 visited 값을 true로 변경합니다.
      2. 해당 번호의 친구들 각각에 대해 아직 각 번호를 방문하지 않았다면 재귀함수를 통해 각 번호의 친구들을 방문합니다.
      3. 만약 해당 친구의 번호에서 재귀함수를 통해 방문한 친구의 수가 5라면 A,B,C,D,E 관계가 성립되므로 해당 관계가 존재하는지를 나타내는 변수 isRelation의 값을 True로 변경하고 해당 함수를 끝냅니다.
      4. 만약 해당 친구의 번호에서 A,B,C,D,E 관계가 성립되지 않는다면 방문한 번호들의 visited 값을 false로 변경하고 다음 친구의 번호에 대해 탐색합니다.
4. 3번의 반복문에서 만약 한 번호에서라도 A,B,C,D,E 관계가 있다고 확인이 되면 1을 출력하고 그렇지 않다면 0을 출력합니다.