[Baekjoon] 12893_적의 적

Gold IV

문제(출처: https://www.acmicpc.net/problem/12893)

---

< 적의 적>

 

문제 풀이 & 생각

 

bfs를 사용해서 우호 관계와 적대 관계를 구분한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _12893_ { // 적의 적
	static ArrayList<ArrayList<Integer>> arr;
	static boolean team[], visited[], flag;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		arr = new ArrayList<>();
		team = new boolean[n];
		visited = new boolean[n];
		flag = false;
		for (int i = 0; i < n; i++) {
			arr.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			arr.get(a).add(b);
			arr.get(b).add(a);
		}

		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				team[i] = true;
				search(i);
			}
		}
		if (flag)
			System.out.println(0);
		else
			System.out.println(1);
	}

	private static void search(int idx) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(idx);

		while (!queue.isEmpty()) {
			int num = queue.poll();
			for (int i = 0; i < arr.get(num).size(); i++) {
				int next = arr.get(num).get(i);
				if (!visited[next]) {
					visited[next] = true;
					team[next] = !team[num];
					queue.add(next);
				} else {
					if (team[num] != !team[next]) {
						flag = true;
						return;
					}
				}
			}
		}
	}
}

 

Main

- 사람의 수(n). 적대관계의 수(m) 입력

- arr : 적대 관계 인접 리스트
  team : 우호, 적대 관계 저장 [true, false끼리 같은 팀]
  visited : 방문 여부
  flag : 이론 성립 여부

- 적대 관계에 있는 사람 a, b 입력 후 인접 리스트 저장

- 사람의 수만큼 탐색하여 아직 방문하지 않은 곳이라면 방문 표시 / team을 true로 저장 / search 함수 호출

- flag 여부에 따라 이론 성립 가능한지 아닌지 출력

 

Search

- queue가 빌 때까지 반복 -> num의 인접 리스트 탐색하여 아직 방문하지 않은 곳이라면 방문 표시 / 현재 사람과 적대 관계로 표시 / queue에 추가 But 이미 방문한 곳이라면 적대 관계가 맞는지 확인하여 적대 관계가 아니라면 이론이 성립하지 않으므로 종료

---

---