[BJ13023] ABCDE

 백준 - 숫자 카드 게임 

문제 링크

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

13023번: ABCDE

 

문제 입출력

5 4
0 1
1 2
2 3
3 4

1

 

문제 풀이

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


public class Main {
	static int ans, N, M;
	static List<List<Integer>> adj = new ArrayList<>();
	static boolean[] visit;


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		for (int i = 0; i < N; i++) adj.add(new ArrayList<>());

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());

			adj.get(from).add(to);
			adj.get(to).add(from);
		}

		for (int i = 0; i < N; i++) dfs(i, 0, 1 << i);

		System.out.println(ans);

	} // end main


	private static void dfs(int n, int cnt, int visit) {
		if (ans == 1) return;

		if (cnt == 4) {
			ans = 1;
			return;
		}

		for (int i : adj.get(n)) {
			if ((visit & 1 << i) == 0) dfs(i, cnt + 1, visit | 1 << i);
		}

	}
}

• 일직선 상에 01234 가 연결되어지느냐의 문제.
• 따라서 cnt 를 따지면 된다.
• 여기서 N 이 2000 이라서 인접행렬로 사용하면 시간초과가 난다..!
• 그래서 연결리스트로 해결해야한다.
• 연결리스트를 사용할 때는 우선적으로 각각 new ArrayList<>() 로 초기화를 해줘야한다.
• 만약 방문하지 않았다면 dfs 탐색을 한다.
• visit 는 비트 마스킹으로 해결하였다.

 

 

 

 

 

 

 

 

 

# 백준 ABCDE bfs

---