알고리즘 스터디 6주차 1

13023

• 알고리즘 : 그래프 탐색
• 난이도 : 골드5

문제

13023

접근

• 친구 간의 관계를 노드 간의 관계로 생각함
• 친구 관계 == 노드 간의 간선
• A-B-E 와 같은 친구의 관계가 있는지 여부
• depth가 2이상이 존재하면 되는 듯하다.

가정

• DFS로 풀어서 Depth가 2이상인지 확인한다.

풀어보기

package org.example;

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

public class Main {
	private static boolean [] visited;
	private static ArrayList<Integer>[] nodes;
	private static int depth = 0;
	private static boolean arrive;
	public static void main(String[] args) throws IOException {
		//dfs로 풀면서 depth가 2이상인 경우를 살핀다.
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String [] NM = reader.readLine().split(" ");
		int N = Integer.parseInt(NM[0]);
		int M = Integer.parseInt(NM[1]);

		nodes = new ArrayList[N];
		visited = new boolean[N];
		for(int i = 0; i < N; i++) {
			nodes[i] = new ArrayList<>();
		}
		for(int i = 0; i < M; i++){
			String[] friends = reader.readLine().split(" ");
			int start = Integer.parseInt(friends[0]);
			int end = Integer.parseInt(friends[1]);
			nodes[start].add(end);
			nodes[end].add(start);
		}

		for(int i = 0; i < N; i++) {
			dfs(i, depth);
			if(arrive) break;
		}
		if(arrive) System.out.println(1);
		else System.out.println(0);
	}

	public static void dfs(int start, int nextDepth){
		if(visited[start]){ return;}
		visited[start] = true;
		if(nextDepth == 4 || arrive){
        // depth 가 4가 되면 arrive는 true 가 되어야 한다.
			arrive = true;
			return;
		}
		for(int i : nodes[start]){
			if(!visited[i]){
            // nodes의 list를 순회함.
				dfs(i, nextDepth + 1);
			}
		}
        // 여기 까지 오면 depth 가 4가 안된다는 것, 따라서 다음 배열의 순회를 위해 false로 바꿔준다. 
		visited[start] = false;
	}

}

시행착오

• depth가 2가 아니라 4가 되어야한다.
• A - B - C - D - E (A는 0으로 가정)

참고자료

• 함께 보면 좋은 글, 링크 등.