[백준] code.plus(큐와 그래프,JAVA)13023번, ABCDE

문제 링크

13023번: ABCDE

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에서 그래프와 DFS를 통하여 문제를 해결하였습니다.

DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.

자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

이 문제에 핵심은

1. 문제에 나온 규칙을 만족하면 1을 만족하지 못하면 0을 결과로 출력합니다.

2. 같은 친구 관계는 두 번 이상 존재하지 않는다.

3. 친구 관계이기 때문에 입력되는 관계는 양방향입니다.

 

처음 이 문제를 이해할 때는 이해가 되지 않아서 무슨 내용인지 이해하는데만 시간을 많이 소요한 것 같습니다.ㅜ^ㅜ.

 

예제입력에 대한 내용을 그림으로 표현하다가 이 문제에 규칙이 무슨 내용인지 이해가 되었습니다.

 

예제입력2을 그림으로 표현하면

위 그림에서 규칙에 맞게 적용되도록 관계를 설정하면

위 그래프처럼 어느 한 노드에서 출발하여 다른 노드(도달하지 않했던 노드)로 4번 이동하면 규칙에 만족하는 것입니다.

이 과정을 구현하기 위해 저는 DFS(깊이 우선 탐색)을 통해 구현하였습니다.

 

그래프에 대한 내용을 정의하기 위해 ArrayList<ArrayList<Integer>>의 형태로 리스트를 만들어주었습니다.

위와 같이 정의하여 데이터를 저장하면 각 정점이 어떤 정점으로 이동하는지 간단하게 저장할 수 있습니다.

예를 들어 

1 -> 4

1 -> 3

2 -> 5

3 -> 4

ArrayList<ArrayList<Integer>>의 저장되는 모습은 리스트 안에 리스트가 포함되는 형식으로 저장됩니다.

정점
1	3	4
2	5
3	1	4
4	1	4
5	2

 

DFS를 구현할 때 어떤 노드를 먼저 탐색할지 기준을 정해야하는데 이 문제에서는 기준이 존재하지 않기 때문에 모든 노드에서 DFS를 진행 및 모든 경우를 탐색하여 규칙에 만족하는지 확인하도록 구현하였습니다.

 

처음에 노드 0으로 시작할 때

노드 1에서 시작할 때

노드 1에서 시작할 때 규칙을 만족하기 때문에 DFS탐색을 중지하고 결과를 1로 출력합니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 친구들의 관계를 ArrayList<ArrayList<Integer>>에 저장합니다.

2. DFS(깊이 우선 탐색)을 이용하여 시작 노드 0~N-1까지 모든 경우를 탐색합니다.

3. 탐색 중 규칙에 만족하는 경우가 존재할 경우 탐색을 종료하고 1을 결과로 출력합니다.

4. 모든 탐색이 종료되었지만 규칙이 만족하지 못하면 0을 결과로 출력합니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해서 친구에 대한 입력값을 나누었습니다.
• DFS탐색으로 규칙에 만족하는지 확인하는 dfs함수를 사용하였습니다.
• DFS탐색 중 Count가 5가 되면 규칙에 만족하여 1를 출력하고 시스템을 종료하였습니다.
• DFS 탐색이 끝나도 규칙에 만족하지 못하면 0을 결과로 출력하였습니다.

• dfs 함수는 재귀와 깊이 우선 탐색을 이용하여 구현하였습니다.
• dfs는 Count=5이면 문제에 규칙에 만족한다고 판단하고 결과를 출력하고 시스템을 종료하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int N,M;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();	//친구 관계 저장 리스트
	static boolean[] visited;		//해당 친구 도달했는지 확인 배열
	public static void main(String[] arg) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		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());
            		//양방향으로 a,b일 때와 b,a를 모두 저장
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		
		br.close();
		
		for(int i=0;i<N;i++) {		//각 노드 기준 DFS 탐색 시작
			visited = new boolean[N];
			dfs(i,1);
		}

		
		System.out.println("0\n");		//DFS탐색 후 규칙 만족 안할 때 0 출력

	}
    	//DFS를 통해 규칙을 만족하면 1을 출력하는 함수
	static void dfs(int cur, int count) {
		if(count==5) {	//규칙 만족할 때
			System.out.println("1");		//결과 1 출력
			System.exit(0);		//시스템 종료
		}
		visited[cur] = true;		//해당 친구 도달 완료
		for(int i=0;i<graph.get(cur).size();i++) {
			if(!visited[graph.get(cur).get(i)]) {	//다른 친구 도달 가능시
				dfs(graph.get(cur).get(i),count+1);
			}
		}
		visited[cur] = false;	//해당 친구 도달 취소
		return;
	}
}