문제
지문
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.
도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.
입력
첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. 둘째 줄에 여행 계획에 속한 도시들의 수 M이 주어진다. M은 1000이하이다. 다음 N개의 줄에는 N개의 정수가 주어진다. i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 1이면 연결된 것이고 0이면 연결이 되지 않은 것이다. A와 B가 연결되었으면 B와 A도 연결되어 있다. 마지막 줄에는 여행 계획이 주어진다. 도시의 번호는 1부터 N까지 차례대로 매겨져 있다.
출력
첫 줄에 가능하면 YES 불가능하면 NO를 출력한다.
입출력 예시
입력
3 -> 도시의 수 N
3 -> 여행 계획 도시의 수 M
// i번 도시와 j번 도시의 연결 정보
// 1 : 연결, 0 : 연결X
0 1 0
1 0 1
0 1 0
// 여행 계획
1 2 3
출력
YES
문제 정리
목표
노드 수 N개의 그래프에서 주어진 M개의 노드가 연결되어있는가? = 같은 그룹인가?
조건
1. A->B 연결이라면 B->A도 연결되어있음.
=> 무방향 그래프
2. 1이면 연결, 0이면 연결 X
=> 가중치가 없는 그래프
3. 같은 도시 여러 번 방문 가능
=> 연결 여부(그룹핑)만 필요
아이디어
변수 설정
[입력 변수]
int n //도시 수 n (n<=200)
int m //여행 계획에 속한 도시들의 수 m (m<=1000)
int[] plan //여행 계획 도시 순서대로 담을 배열
.
[추가 설정 변수]
static int[] parent //부모 노드 번호 담을 배열
.
[출력 변수]
String ans //출력 담을 문자열 : YES로 초기확ㄱㄱ
고려 사항
- 도시 번호 : 1부터 시작
=> 배열 값을 받을 필요 없이 인덱스 = 노드 번호로 여김
=> 인덱스 주의!- 순서대로 주어지는 계획 그대로 이행해야 함
=> 그러나, 도시에 여러 번 방문 가능 / 무방향 그래프이므로 해당 케이스에서는 고려하지 않아도 됨
- ex) E C B C D 라면 E-A-B-C-B-C-B-D 가능
=> 계획에 있는 도시를 지나쳐가는 것도 가능
로직
- 주어진 노드들이 전부 같은 그룹에 속해있는지 여부 판단
=> 유니온 파인드를 써야겠다- 연결되어있다면(인풋이 1) 작은 값으로 루트를 합치자
- 계획에 포함된 번호(도시 번호)가 같은 루트인지 판별
코드
초기 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//여러 번 방문 가능 = 같은 그래프에 속해있으면 연결 가능
public class Main {
static int[] parent;
// static int[] origin;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
// origin = new int[n];
parent = new int[n];
for (int i = 0; i < n; i++) {
// origin[i]=i;
parent[i] = i;
}
int m = Integer.parseInt(br.readLine()); // 도시 수
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int info = Integer.parseInt(st.nextToken());
if (info == 1) {
union(i, j);
}
}
}
st = new StringTokenizer(br.readLine());
int[] plan = new int[m];
for (int i = 0; i < m; i++) {
int num = Integer.parseInt(st.nextToken());
plan[i] = num - 1;
}
String ans = "YES";
for (int i = 1; i < m; i++) {
if (parent[plan[i]] != parent[plan[i - 1]]) {
ans = "NO";
break;
}
}
System.out.println(ans);
}
static int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
static void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootY] = rootX;
}
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
}문제점
루트 노드를 가리키는 것이 아니라, 직계 부모만 담고 있음
.[예시 인풋] 5 8 0 1 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 0 1 4 4 4 2 5 3 5 [오답 출력] NO [정답 출력] YES위 예시를 실행하면
parent : {2,0,2,2,2}로 보임
=> parent에 루트를 저장하는 로직이 필요
전체코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Gold_1976 {
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int m = Integer.parseInt(br.readLine()); // 도시 수
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int info = Integer.parseInt(st.nextToken());
if (info == 1) {
union2(i, j);
}
}
}
st = new StringTokenizer(br.readLine());
int[] plan = new int[m];
for (int i = 0; i < m; i++) {
int num = Integer.parseInt(st.nextToken());
plan[i] = num - 1;
}
// 루트 노드로 재정렬
for (int i = 0; i < n; i++) {
find(i); // 모든 노드 경로 압축
}
String ans = "YES";
for (int i = 1; i < m; i++) {
if (parent[plan[i]] != parent[plan[i - 1]]) {
ans = "NO";
break;
}
}
System.out.println(ans);
}
static int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
static void union2(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if(rootX>rootY) {
int temp = rootY;
rootY=rootX;
rootX=temp;
}
parent[rootY] = rootX;
}
}
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
}상세 코드
union
static void union2(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if(rootX>rootY) {
int temp = rootY;
rootY=rootX;
rootX=temp;
}
parent[rootY] = rootX;
}
}이 때, 항상 작은 쪽을 루트노드로 정리
루트 노드 찾기
static int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}연결되어있다면(input 1) 합치기
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int info = Integer.parseInt(st.nextToken());
if (info == 1) {
union2(i, j);
}
}
}루트 노드로 재정렬
for (int i = 0; i < n; i++) {
find(i); // 모든 노드 경로 압축
}계획 점검
for (int i = 1; i < m; i++) {
if (parent[plan[i]] != parent[plan[i - 1]]) {
ans = "NO";
break;
}
}다른 방법
BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int n, m; //도시 수
static List<Integer>[] graph;
static boolean[] visited;
static Queue<Integer> q;
static int[] plan;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
m=Integer.parseInt(br.readLine());
graph=new ArrayList[n];
for(int i = 0;i<n;i++){
graph[i]=new ArrayList<>();
}//초기화
visited=new boolean[n];
StringTokenizer st;
for(int i = 0;i<n;i++){
st =new StringTokenizer(br.readLine());
for(int j = 0;j<n;j++){
int info = Integer.parseInt(st.nextToken());
if(info==1){
graph[i].add(j);
graph[j].add(i);
}
}
}
plan = new int[m];
st = new StringTokenizer(br.readLine());
for(int i = 0;i<m;i++){
plan[i]=Integer.parseInt(st.nextToken())-1;
}
bfs(plan[0]);
String ans = "YES";
for(int i = 0;i<m;i++){
if(!visited[plan[i]]){
ans="NO";
break;
}
}
System.out.println(ans);
}//main 끝
public static void bfs(int v){
q=new LinkedList<>();
q.add(v);
visited[v]=true;
while(!q.isEmpty()){
int curr = q.poll();
for(int w:graph[curr]){
if(!visited[w]){
q.add(w);
visited[w]=true;
}
}
}
}
}DFS
package day0319;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_1976_DFS {
static int n, m; // 도시 수
static List<Integer>[] graph;
static boolean[] visited;
static Queue<Integer> q;
static int[] plan;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
} // 초기화
visited = new boolean[n];
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int info = Integer.parseInt(st.nextToken());
if (info == 1) {
graph[i].add(j);
graph[j].add(i);
}
}
}
plan = new int[m];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) {
plan[i] = Integer.parseInt(st.nextToken()) - 1;
}
dfs(plan[0]);
String ans = "YES";
for (int i = 0; i < m; i++) {
if (!visited[plan[i]]) {
ans = "NO";
break;
}
}
System.out.println(ans);
}// main 끝
public static void dfs(int v) {
visited[v] = true;
for (int curr : graph[v]) {
if (!visited[curr]) {
dfs(curr);
}
}
}
}
성능 비교
- DFS
- BFS
- 유니온파인드
정리
- 유니온 파인드를 배울 수 있는 기초 문제
- DFS가 BFS,유니온파인드보다 메모리 / 시간 측면에서 불리
