[Baekjoon] 5938_Daisy Chains in the Field

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

---

< Daisy Chains in the Field >

 

문제 풀이 

 

bfs를 활용하여 1번 소와 연결되지 않은 소를 찾는다.

 

my solution (Java)

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

public class _5938_ { // Daisy Chains in the Field

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

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

		boolean visited[] = new boolean[n + 1];

		ArrayList<ArrayList<Integer>> list = new ArrayList<>();

		for (int i = 0; i < n + 1; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());

			int c1 = Integer.parseInt(st.nextToken());
			int c2 = Integer.parseInt(st.nextToken());

			list.get(c1).add(c2);
			list.get(c2).add(c1);
		}

		bfs(visited, list);

		boolean flag = false;
		for (int i = 1; i < n + 1; i++) {
			if (!visited[i]) {
				flag = true;
				bw.write(i + "\n");
			}
		}
		if (!flag) {
			bw.write("0");
		}

		bw.flush();
	}

	private static void bfs(boolean[] visited, ArrayList<ArrayList<Integer>> list) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);
		visited[1] = true;

		while (!queue.isEmpty()) {
			int info = queue.poll();

			for (int i = 0; i < list.get(info).size(); i++) {
				if (!visited[list.get(info).get(i)]) {
					visited[list.get(info).get(i)] = true;
					queue.add(list.get(info).get(i));
				}
			}
		}
	}
}

변수)
n, m : 소의 수, 연결된 소의 수
visited : 1번과 연결 여부
list : 연결된 소 정보
c1, c2 : 연결된 소 입력값 
flag : 연결 여부

 

Main

소의 수와 연결된 소의 수를 입력받는다. 연결된 소의 수만큼 연결된 소 정보를 입력받아 ArrayList에 양방향으로 저장한다. bfs 함수를 호출한 후 visited를 탐색하며 1번과 연결되지 않은 소의 번호를 출력한다. 단, 1번과 연결되지 않은 소가 한 마리도 없다면 0을 출력한다.

 

bfs(연결 여부, 연결 정보)

Queue에 1 저장과 visited[1]을 true로 저장 후 Queue가 빌 때까지 다음 과정을 반복한다.

 

1) queue poll

2) ArrayList에서 값을 찾아 탐색하며 아직 연결 여부를 확인하지 않은 번호라면 true로 저장 후 queue에 추가

---

---