Coding/알고리즘
[알고리즘 TIL] 1707. 이분 그래프
kangplay
2025. 2. 20. 12:47
문제
https://www.acmicpc.net/problem/1707
구현(첫번째 시도)
import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
public class Q1707_이분그래프 {
static BufferedWriter bw;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
int K = Integer.parseInt(br.readLine());
for (int i = 0; i < K; i++) {
String[] inputStr = br.readLine().split(" ");
int V = Integer.parseInt(inputStr[0]);
int E = Integer.parseInt(inputStr[1]);
HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
for (int j = 0; j < E; j++) {
inputStr = br.readLine().split(" ");
int startNode = Integer.parseInt(inputStr[0]);
int endNode = Integer.parseInt(inputStr[1]);
addEdge(graph, startNode, endNode);
addEdge(graph, endNode, startNode);
}
dfs(graph, V);
}
bw.flush();
bw.close();
br.close();
}
private static void dfs(HashMap<Integer, ArrayList<Integer>> graph, int v) throws IOException {
LinkedList<Integer[]> stack = new LinkedList<>();
HashSet<Integer> visited = new HashSet<>();
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
stack.addLast(new Integer[]{1, 1});
/**
* stack에 Node와 들어가야할 배열 번호 저장
* 1. 각 Node를 순회하면서 인접한 노드들에 자기와 다른 배열 번호를 부여하여 스택에 저장
* 2. 자기가 부여받은 배열 번호에 맞게 저장
* 3. 마지막에 각 배열을 dfs로 순회하며 인접한 노드들이 있는지 확인
*/
while (!stack.isEmpty()) {
Integer[] peek = stack.getLast();
stack.removeLast();
Integer peekNode = peek[0];
Integer listNum = peek[1];
if (visited.contains(peekNode)) continue;
visited.add(peekNode);
//2
if (listNum == 1) list1.add(peekNode);
else list2.add(peekNode);
ArrayList<Integer> nextNodes = graph.get(peekNode);
for (Integer nextNode : nextNodes) {
//1
if (listNum == 1) stack.add(new Integer[]{nextNode, 2});
else stack.add(new Integer[]{nextNode, 1});
}
}
//3
boolean flag1 = checkIsBinaryGraph(list1, graph);
boolean flag2 = checkIsBinaryGraph(list2, graph);
if (flag1 && flag2) bw.write("YES\n");
else bw.write("NO\n");
}
private static boolean checkIsBinaryGraph(ArrayList<Integer> list, HashMap<Integer, ArrayList<Integer>> graph) {
boolean flag = true;
for (Integer node : list) {
ArrayList<Integer> adjNodes = graph.get(node);
for (Integer adjNode : adjNodes) {
if (list.contains(adjNode)) flag = false;
}
}
return flag;
}
private static void addEdge(HashMap<Integer, ArrayList<Integer>> graph, int startNode, int endNode) {
if (!graph.containsKey(startNode)) {
ArrayList<Integer> nodes = new ArrayList<>();
nodes.add(endNode);
graph.put(startNode, nodes);
return;
}
ArrayList nodes = graph.get(startNode);
nodes.add(endNode);
graph.put(startNode, nodes);
}
}첫번째로 시도한 방법은 다음과 같다.
1. 각 Node를 순회하면서 인접한 노드들에 자기와 다른 배열 번호를 부여하여 스택에 저장
2. 자기가 부여받은 배열 번호에 맞게 저장
3. 마지막에 각 배열을 dfs로 순회하며 인접한 노드들이 있는지 확인하지만 내 방법에 문제는 다음과 같다.
1. DFS에서 모든 노드를 방문하지 않을 가능성이 있음.
그래프가 연결되지 않은 경우, 일부 노드를 방문하지 않을 수 있다. 따라서 모든 노드를 방문할 수 있도록, 각 노드에 대해 DFS를 수행해야 한다.
for (int node = 1; node <= V; node++) {
if (colors[node] == 0) { // 방문하지 않은 노드에 대해 DFS 수행
dfs(node, 1);
}
}2. checkIsBinaryGraph()로 인한 O(V^2)
DFS 내에서 이미 색을 다르게 부여하면서 탐색했기 때문에 별도의 검사가 필요 없다. DFS 과정에서 서로 같은 색의 노드가 인접해 있는지를 바로 판별하면 된다.
while (!stack.isEmpty()) {
int node = stack.pop();
int currentColor = colors[node];
for (Integer nextNode : graph.getOrDefault(node, new ArrayList<>())) {
if (colors[nextNode] == 0) {
colors[nextNode] = 3 - currentColor; // 1이면 2, 2이면 1
stack.push(nextNode);
} else if (colors[nextNode] == currentColor) {
isBipartite = false;
return; // 🚀 바로 탈출하여 불필요한 탐색 방지
}
}
}
구현(두번째 시도)
import java.io.*;
import java.util.*;
public class Q1707_이분그래프 {
static BufferedWriter bw;
static HashMap<Integer, ArrayList<Integer>> graph;
static int[] colors; // 0: 방문 안 함, 1: 그룹1, 2: 그룹2
static boolean isBipartite;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
int K = Integer.parseInt(br.readLine());
for (int i = 0; i < K; i++) {
String[] inputStr = br.readLine().split(" ");
int V = Integer.parseInt(inputStr[0]);
int E = Integer.parseInt(inputStr[1]);
graph = new HashMap<>();
colors = new int[V + 1]; // 1-based index
for (int j = 0; j < E; j++) {
inputStr = br.readLine().split(" ");
int startNode = Integer.parseInt(inputStr[0]);
int endNode = Integer.parseInt(inputStr[1]);
addEdge(startNode, endNode);
addEdge(endNode, startNode);
}
isBipartite = true;
for (int node = 1; node <= V; node++) {
if (colors[node] == 0) { // 방문하지 않은 노드에 대해 DFS 수행
iterativeDFS(node);
}
}
bw.write(isBipartite ? "YES\n" : "NO\n");
}
bw.flush();
bw.close();
br.close();
}
private static void iterativeDFS(int startNode) {
Stack<Integer> stack = new Stack<>();
stack.push(startNode);
colors[startNode] = 1; // 첫 번째 노드를 그룹 1로 설정
while (!stack.isEmpty()) {
int node = stack.pop();
int currentColor = colors[node];
for (Integer nextNode : graph.getOrDefault(node, new ArrayList<>())) {
if (colors[nextNode] == 0) {
colors[nextNode] = 3 - currentColor; // 1이면 2, 2이면 1
stack.push(nextNode);
} else if (colors[nextNode] == currentColor) {
isBipartite = false;
return;
}
}
}
}
private static void addEdge(int startNode, int endNode) {
graph.putIfAbsent(startNode, new ArrayList<>());
graph.get(startNode).add(endNode);
}
}느낀 점
1. 값 복사와 얕은 복사
위와 같이 int, double 같은 기본 타입은 인자로 값을 넘길 때, 값 복사가 일어나서 해당 값을 수정하여도 원본 값에는 영향을 미치지 않는다. 하지만 List 같은 객체를 넘기면 참조 복사가 일어나기 때문에 값을 수정하면 원본 값에도 영향을 미친다. clone() 메소드를 활용하여 깊은 복사를 적용하면 원본 값에 영향을 미치지 않도록 할 수 있다.
* String, Boolean, Integer 같은 타입은 불변 객체이기 때문에 참조값이 복사되지만, 값 복사처럼 동작한다. 즉, 원본이 변경되지 않으며, 새로운 문자열 객체를 생성하여 사용한다!
2. || 와 &&
||는 논리 OR 연산자로, 하나라도 true이면 결과는 true이다. 반대로 &&는 논리 AND 연산자로, 둘 다 false여야지 결과가 true이다.