백준 13023번 자바

문제

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

13023번: ABCDE

 

1. 그래프와 DFS

이 문제역시 그래프와 DFS에대한 개념을 알고있어야 풀수 있다. 해당 개념에 대한 간략한 설명을 아래에 링크를 추가했다.

https://ahlight.tistory.com/82

 

2. 접근 방식

실제 문제를 푸는 시간보다 문제를 이해하는데 더 오랜 시간이 걸렸던 문제다. 예제의 친구관계를 그래프로 그려보다 문제에서 원하는 조건이 무엇인지 파악했다.

- 문제에서 친구관계가 뜻하는 바는 무방향 그래프이다.

- 간선으로 이어진 노드는 모두 인접노드라고 볼 수 있다.

- 인접한 노드로 이동하는 횟수가 문제에서의 조건처럼 4회 이상이면 1을 출력, 아니면 0을 출력한다.

- 단, 모든 노드에서 출발했을 때 4회 이상이 아니고 어느 곳에서든 4회 이상이면 1을 출력한다.

- 아래 그림에서 예제4의 경우 노드(2)에서 출발한 경우만 표시를 했고, 다른 노드에서 출발할 때 4회 미만인 경우도 존재한다.

 

3. 인접리스트를 활용한 구현

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

public class Main13023 {
	static int N,M;
	static List<Integer>[] adjacencyList; // 인접노드 배열
	static boolean[] visited;
	static int ans = 0;

	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());
		adjacencyList = new ArrayList[N];
		visited = new boolean[N];
		
		for (int i=0; i<N; i++) {
			adjacencyList[i] = new ArrayList<Integer>();
		}
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adjacencyList[a].add(b);
			adjacencyList[b].add(a);
		}
		
        // 0~N-1까지 차례대로 출발
		for (int i=0; i<N; i++) {
			dfs(i, 0);
			if (ans == 1) {
				break;
			}
		}
		
		System.out.println(ans);
	}
	
	public static void dfs(int node, int depth) {
		if (depth == 4 || ans == 1) {
			ans = 1;
			return;
		}
		
		visited[node] = true;
		for (int i=0; i<adjacencyList[node].size(); i++) {
			if (!visited[adjacencyList[node].get(i)]) {
				dfs(adjacencyList[node].get(i), depth + 1);
			}
		}
		visited[node] = false;
	}
}

 

정리 : 문제를 이해하는데 시간이 많이 걸렸다. 다행히 접근 방식이 타당했다. 다만 처음 제출했을 때 시간초과가 났고 해당 부분을 해결하는데 애를 먹었다. 재귀에서 조건을 제한시켜 시간을 단축하는 방식을 항상 고려해야겠다.