https://www.acmicpc.net/problem/13023
모든 노드를 시작점으로 하고 탐색해서 깊이가 4가 되는 때를 찾음.
처음 그래프를 구현할 때 배열을 썼는데 배열로 구현을 하면 시간초과가 생겨서 리스트로 다시 구현을 했다.
궁금한 점은 배열로 구현했을 땐 분기점의 노드의 상태를 true에서 false로 변환해주지 않았는데 리스트로 구현했을 땐 필요했다는 것이다.
내 코드
메모리 : 19840 KB
시간 : 264 ms
코드 길이 : 1532 B
[내 코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N;
static ArrayList<Integer>[] list;
static boolean[] isVisit;
static boolean result = false;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
st = new StringTokenizer(br.readLine());
//사람의 수
N = Integer.parseInt(st.nextToken());
//관계의 수
int M = Integer.parseInt(st.nextToken());
list = new ArrayList[N];
for(int i = 0; i < N; i++)
list[i] = new ArrayList<Integer>();
for(int m = 0; m < M; m++) {
st = new StringTokenizer(br.readLine());
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
list[i].add(j);
list[j].add(i);
}
for(int n = 0; n < N; n++) {
if(result == false) {
isVisit = new boolean[N];
DFS(n, 0);
}
}
if(result == true)
sb.append(1);
else
sb.append(0);
System.out.print(sb);
}
//깊이 우선 탐색
public static void DFS(int node, int length) {
if(length == 4) {
result = true;
return;
}
isVisit[node] = true;
for(int i = 0; i < list[node].size(); i++) {
int nextNode = list[node].get(i);
if(isVisit[nextNode] == false) {
//true로 변환 후
isVisit[nextNode] = true;
//그 상태를 기준으로 다음 탐색 시작
DFS(nextNode, length + 1);
//분기점인 노드인 경우 true이면 다른 분기의 노드를 탐색할 수 없으므로 false로 바꿔준다.
isVisit[nextNode] = false;
}
}
}
}
1등 코드
메모리 : 12504 KB
시간 : 156 ms
코드길이 : 1500 B
[상위권 코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int answer = 0;
static int N, M;
static boolean [] visited;
static Node[] adjList;
static class Node {
int vertex;
Node link;
public Node(int vertex, Node link) {
this.vertex = vertex;
this.link = link;
}
}
static void dfs(int idx, int cnt) {
visited[idx] = true;
if (cnt == 4){
answer = 1;
return;
}
for (Node temp = adjList[idx]; temp!= null;temp = temp.link){
if (!visited[temp.vertex])
dfs(temp.vertex, cnt+1);
}
visited[idx]=false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
visited = new boolean[N];
adjList = new Node[N];
int from, to;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
adjList[from] = new Node(to, adjList[from]);
adjList[to] = new Node(from, adjList[to]);
}
for (int i = 0; i < N; i++) {
dfs(i, 0);
}
System.out.println(answer);
}
}
'백준 > DFS BFS' 카테고리의 다른 글
[백준] 4803 : 트리 (0) | 2024.09.06 |
---|---|
[백준] 1697 : 숨바꼭질 (0) | 2023.04.21 |
[백준] 11724 : 연결요소의 개수 (0) | 2023.04.21 |
[백준] 13549 : 숨바꼭질 3 (0) | 2023.04.19 |
[백준] 1260 : DFS와 BFS (0) | 2023.04.17 |