반응형
소개
- 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
- TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
- 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.
문제 & 키워드
- 백준 - 사자와 토끼 (문제 링크)
- 이분 그래프
- 그래프 탐색
- 깊이 우선 탐색 (DFS)
문제 설명
- 사자와 토끼는 전국적으로 인기를 끌고 있는 재밌는 보드게임이다.
- 사자와 토끼를 즐기기 위해서는 2명의 플레이어와 1명의 심판이 필요하다.
- 보드판은 N개의 수풀과 M개의 오솔길로 이루어져 있다.
- 오솔길은 서로 다른 두 수풀을 양방향으로 연결하며, 어떤 수풀에서 다른 수풀까지 1개 이상의 오솔길을 통하면 반드시 도달할 수 있다.
게임은 다음과 같은 순서로 이루어진다.
- 심판이 사자와 토끼의 초기 위치를 각각 어느 수풀로 할지 정한다. 사자와 토끼의 초기 위치는 같을 수 없으며, 사자의 위치는 사자 플레이어에게만, 토끼의 위치는 토끼 플레이어에게만 알려준다.
- 매 턴마다, 사자와 토끼는 현재 위치한 수풀에서 오솔길 1개를 따라 이동해야 한다. 두 플레이어는 자신의 말을 이동할 위치를 심판에게만 말한다. 이동하지 않을 수는 없다.
- 이동한 후, 사자와 토끼가 같은 수풀에 있다면 사자가 토끼를 잡아먹어 게임이 끝난다. 그렇지 않다면, 다시 2로 돌아가 턴을 계속하여 진행한다. 물론 게임이 끝나지 않는 이상, 이동 후에도 두 플레이어는 상대 말의 위치를 알 수 없다. 또한, 사자는 오솔길 위에서는 토끼를 볼 수 없기 때문에, 같은 오솔길을 통해 이동하여도 서로 다른 수풀에 도착했다면 게임이 끝나지 않는다.
보드의 모양과 사자와 토끼의 초기 위치에 따라서, 어떻게 움직여도 영원히 게임이 끝나지 않는 경우가 있다는 것을 발견했다.
보드판의 모양이 주어질 때, 어떻게 움직여도 영원히 게임이 끝나지 않는 초기 위치의 경우의 수가 몇 가지인지 구해보자.
문제 접근
- 이 문제는 보드판을 그래프로 표현하고, 이를 통해 두 그룹으로 나눌 수 있는지 확인하는 방식으로 해결할 수 있습니다.
- 두 그룹으로 나눌 수 있다면 서로가 같은 위치로 이동하지 않도록 할 수 있습니다.
- 이런 구조를 이분 그래프라고 하며, 이분 그래프인지 확인하는 과정에서 DFS(깊이 우선 탐색)을 사용합니다.
풀이 - dfs 활용
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 nodeCount, edgeCount, teamA, teamB;
private static boolean[] visited;
private static int[] group;
private static ArrayList<Integer>[] graph;
private static boolean isNotBipartite;
public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
StringTokenizer st = new StringTokenizer(br.readLine());
nodeCount = Integer.parseInt(st.nextToken());
edgeCount = Integer.parseInt(st.nextToken());
visited = new boolean[nodeCount + 1];
group = new int[nodeCount + 1];
graph = new ArrayList[nodeCount + 1];
teamA = 1; // 초기화
// 인접 리스트 초기화
for (int i = 1; i <= nodeCount; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < edgeCount; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph[start].add(end);
graph[end].add(start);
}
for (int i = 1; i <= nodeCount; i++) {
if (isNotBipartite) {
System.out.println(0);
return;
} else if (!visited[i]) {
dfs(i);
}
}
System.out.println(teamA * teamB * 2);
} catch (IOException e) {
e.printStackTrace();
}
}
private static void dfs(int index) {
visited[index] = true;
for (int num : graph[index]) {
if (!visited[num]) {
int team = (group[index] + 1) % 2;
if (team == 0) {
teamA++;
} else {
teamB++;
}
group[num] = team;
dfs(num);
} else {
if (group[num] == group[index]) {
isNotBipartite = true;
}
}
}
}
}풀이 설명
- 그래프 초기화
- 입력으로 주어진 노드와 간선의 수를 바탕으로 그래프를 인접 리스트 형태로 초기화합니다.
- visited 배열을 초기화하여 방문 여부를 추적하고, group 배열을 초기화하여 각 노드의 그룹을 저장합니다.
- DFS 탐색 및 이분 그래프 확인
- 각 노드를 DFS로 탐색하며, 인접한 노드를 다른 그룹으로 설정합니다.
- 만약 탐색 도중 같은 그룹 내에 간선이 존재하면 isNotBipartite를 true로 설정하여 이분 그래프가 아님을 표시합니다.
- 결과 계산
- DFS 탐색 후, 만약 그래프가 이분 그래프가 아니라면 0을 출력합니다.
- 이분 그래프라면 두 그룹 A와 B의 크기를 곱하고 2를 곱하여 모든 가능한 초기 위치의 경우의 수를 계산하여 출력합니다.
마무리하며
- 이번 문제를 통해 이분 그래프를 확인하고, DFS를 활용하여 그래프 탐색을 수행하는 방법을 학습하였습니다.
- 그래프의 각 노드를 그룹으로 나누고, 이를 통해 문제를 해결하는 과정이 중요합니다.
