[BOJ] 13023번 ABCDE

풀이

아이디어

문제에서 요구하는 건 서로 다른 정점의 간선의 연속적인 깊이가 4인 간선들이 있는지를 찾는 것이다. 모든 정점이 출발점이 되는 경우를 구해야되고 인접한 정점들을 차례로 DFS로 들어가는 깊이를 구해야한다. 이때 방문했던 노드를 방문하는 사이클이 발생하면 안된다.

구현

처음에 정점 인접행렬로 이차원배열에 모든 노드들에 대한 모든 간선들을 입력해서 각 모든 노드를 출발점으로 하는 DFS를 호출했고 방문 배열로 방문한 노드는 다시 가지 않도록 했다. 기저조건은 문제에서 요구한 연속적인 깊이 4가 되는 경우로 설정했다.
하지만 시간초과가 났고 정점 인접리스트로 바꿨다. 한 정점에서 다른 모든 정점을 가는 경우 -> 인접리스트를 이용해서 연결된 정점만 확인하는 방법으로 바꿔서 풀었다.

정점 인접행렬 코드 -> 시간초과

/**
 * ABCDE
 * UNION FIND
 * A B C D E
 * 서로 다른 정점의 간선의 연속적인 깊이가 4인  그래프를 찾아라
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	

	private static int[][] map;
	private static int M;
	private static int N;
	private static boolean[] vis;
	private static boolean flag;
	

	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()); //관계의 수

		
		//정점 인접 리스트
		map = new int[N][N];
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
				int s = Integer.parseInt(st.nextToken());
				int e = Integer.parseInt(st.nextToken());
				map[s][e] = 1; //간선 표시
				map[e][s] = 1; //간선 표시
		}//입력완료
		//재귀 방문 배열: 각 인덱스를 숫자 번호로 하고 방문 여부를 체크한다.
		//방문한 곳으로는 깊이 탐색을 하지 않는다.
		//dfs 호출시 각 시작정점을 넘겨준다.
		flag = false;
		for(int i = 0; i < N; i++) {
			if(flag) break;
			vis = new boolean[N];
			vis[i] = true;
			dfs(i, 0);
		}
		if(flag) System.out.println(1);
		else System.out.println(0);

	}
	public static void dfs(int sNode, int cnt) {
		if(flag) return; 
		if(cnt == 4) { //깊이(cnt)가 4개가 되면 멈춘다.
			flag = true;
			return;
		}
		else {
			for(int i = 0; i < N; i++) {
				if(map[sNode][i] == 1) { //간선이 있다면 깊이를 +1시키고 그 정점 (행)으로 넘어간다.
					if(vis[i]) continue;
					vis[i] = true;
					dfs(i ,cnt+1);
					vis[i] = false;
				}
			}
		}
	}

}

정점 인접 리스트 코드

/**
 * ABCDE
 * A B C D E
 * 서로 다른 정점의 간선의 연속적인 깊이가 4인  연속된 간선들을  찾아라
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
	

	private static int M;
	private static int N;
	private static boolean[] vis;
	private static boolean flag;
	private static ArrayList<ArrayList<Integer>>  arr;
	

	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()); //관계의 수

		
		//정점 인접 행렬 -> 시간초과 -> 인접 리스트

		arr = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			arr.add(new ArrayList<>());
		}
		
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			arr.get(s).add(e);
			arr.get(e).add(s);
		}//입력완료
		//재귀 방문 배열: 각 인덱스를 숫자 번호로 하고 방문 여부를 체크한다.
		//방문한 곳으로는 깊이 탐색을 하지 않는다.
		//dfs 호출시 각 시작정점을 넘겨준다.
		flag = false;
		for(int i = 0; i < N; i++) {
			if(flag) break;
			vis = new boolean[N];
			vis[i] = true;
			dfs(i, 0);
		}
		if(flag) System.out.println(1);
		else System.out.println(0);

	}
	public static void dfs(int sNode, int cnt) {
		if(flag) return; 
		if(cnt == 4) { //깊이(cnt)가 4개가 되면 멈춘다.
			flag = true;
			return;
		}
		else {
			for(int i = 0; i < arr.get(sNode).size(); i++) {
//간선이 있다면 깊이를 +1시키고 그 정점 (행)으로 넘어간다.
				int nextNode = arr.get(sNode).get(i);
				if(vis[nextNode]) continue;
					vis[nextNode] = true;
					dfs(nextNode ,cnt+1);
					vis[nextNode] = false;
			}
		}
	}

}