백준 11724 풀이
https://www.acmicpc.net/problem/11724
오랜만의 그래프 문제이다.
주어진 그래프의 연결 요소를 찾는 문제인데 연결요소가 멀까
위와 같은 그림이 연결 요소이다.
연결 요소가 될 조건은
연결 요소에 속한 모든 정점을 연결하는 경로가 있어야 한다.
또 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.
다음과 같고 그래프 문제이기때문에 dfs 혹은 bfs를 적용해서 풀면 간단하게 풀린다.
또 방향없는 그래프이기 때문에 간선을 이어줄 때 주의해야한다. 이 부분을 캐치하지 못해 시간이 끌렸다.
import java.io.*;
public class Main {
static boolean[] visited;
static boolean[][] visit;
static int[] p;
static int[] ap;
static int[][] arr;
static int min = 1001;
static int n, m;
static int cnt = 0;
static int index = 0;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String line = br.readLine();
String[] nums = line.split(" ");
n = Integer.parseInt(nums[0]);
m = Integer.parseInt(nums[1]);
arr = new int[n + 1][n + 1];
visit = new boolean[n + 1][n + 1];
visited = new boolean[n + 1];
visited[0] = false;
for (int h = 1; h <= n; h++) {
visited[h] = false;
for (int j = 1; j <= n; j++) {
visit[h][j] = false;
}
}
for (int i = 0; i < m; i++) {
String str = br.readLine();
String[] s = str.split(" ");
arr[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = 1;
arr[Integer.parseInt(s[1])][Integer.parseInt(s[0])] = 1;
}
find();
bw.write(Integer.toString(cnt));
br.close();
bw.close();
}
public static void find() {
for (int i = 1; i <= n; i++) {
if (visited[i] == false) {
dfs(i);
cnt++;
}
}
}
public static void dfs(int start) {
visited[start] = true;
for (int i = 1; i <= n; i++) {
if (arr[start][i] == 1 && visited[i] == false) {
dfs(i);
}
}
}
}
Author And Source
이 문제에 관하여(백준 11724 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-11724-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)