성능 요약
메모리: 205512 KB, 시간: 456 ms
분류
백트래킹, 깊이 우선 탐색, 그래프 이론, 그래프 탐색
문제 설명
BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
- A는 B와 친구다.
- B는 C와 친구다.
- C는 D와 친구다.
- D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어
지는 경우는 없다.
출력
문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.
풀이 (DFS)
시간 복잡도 O(N) 공간 복잡도 O(N)
아이디어: 문제에서는 A-B-C-D-E의 관계가 존재하는지 묻고 있기에 이는 곧 그래프 정보에서 깊이가 5인 구간이 존재하는지 여부를 묻는 다고 볼 수 있다. 따라서 DFS(깊이 우선 탐색)을 사용하여 만약 5이상의 깊이를 가지는 구간이 존재한다면 1을 출력시키고 프로그램을 종료시키면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static HashMap<Integer, ArrayList<Integer>> map;
static boolean[] visited;
static int depth;
public static boolean dfs(int node){
depth++;
// 깊이가 5이면 문제에서 원하는 관계가 존재하기에 true
if(depth ==5) return true;
// 현재 노드를 방문한 것으로 표시
visited[node] = true;
// 현재 노드에 인접한 모든 노드를 확인
ArrayList<Integer> nextNodes = map.get(node);
for (Integer nextNode : nextNodes) {
if(!visited[nextNode])
if(dfs(nextNode))
return true;
}
// 깊이 감소
depth--;
visited[node] = false; // 방문 초기화
return false;
}
public static int sti(StringTokenizer st){
return Integer.parseInt(st.nextToken());
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = sti(st), M = sti(st);
map = new HashMap<>();
for (int i = 0; i < N; i++) map.put(i,new ArrayList<>());
boolean ans = false;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int op1 = sti(st), op2 = sti(st);
// 같은 관계는 두번 이상 주어지지 않는다.
map.get(op1).add(op2);
map.get(op2).add(op1);
}
// 깊이가 5면 1 아니면 0
for (int i = 0; i < N; i++) {
visited = new boolean[N];
depth = 0;
if (dfs(i)) {
System.out.println(1);
return;
}
}
System.out.println(0);
}
}참고하여 개선된 풀이 (DFS)
아이디어: static HashMap<Integer, ArrayList<Integer>> map; 자료구조를 단순한 연결 리스트 형식의 자료구조로 변경함으로써 버킷배열, 해시 함수, 재해시 연산을 줄임으로서 오버헤드를 줄여 메모리와 속도를 둘다 개선
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int answer = 0;
static boolean[] visited;
static Node[] map;
static class Node{
int vertex;
Node link;
public Node(int vertex, Node link) {
this.vertex = vertex;
this.link = link;
}
}
static void dfs(int index, int depth){
visited[index] = true;
if(depth==5){
answer =1;
return;
}
for(Node next = map[index]; next!=null; next=next.link){
if(!visited[next.vertex])
dfs(next.vertex,depth+1);
}
visited[index] = false;
}
public static int parseTokenToInt(StringTokenizer st){
return Integer.parseInt(st.nextToken());
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = parseTokenToInt(st), M = parseTokenToInt(st);
map = new Node[N];
visited = new boolean[N];
int head, next;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
head = parseTokenToInt(st);
next = parseTokenToInt(st);
// 같은 관계는 두번 이상 주어지지 않는다.
map[head] = new Node(next, map[head]);
map[next] = new Node(head,map[next]);
}
// 깊이가 5면 1 아니면 0
for (int i = 0; i < N; i++) {
dfs(i,1);
}
System.out.println(answer);
}
}
'PS > Gold' 카테고리의 다른 글
| [Gold V] 숫자고르기 - 2668 (Java) (0) | 2023.08.21 |
|---|---|
| [Gold IV] 연구소 - 14502 (Java) (0) | 2023.08.20 |
| [Gold IV] 치즈 - 2636 (Java) (0) | 2023.08.20 |
| [Gold V] 공주님을 구해라! - 17836 (Java) (0) | 2023.08.17 |
| [Gold V] 숨바꼭질 3 - 13549 (Java) (0) | 2023.08.16 |
