반응형

13023번 ABCDE

https://www.acmicpc.net/problem/13023

 

13023번: ABCDE

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

www.acmicpc.net

 

 

DFS공부하다가 만난 문제 그냥 열심히 구현 하다가

문득 궁금해져서 일반 for문으로 바꾸고 싶어졌었다가 상당히 오랜 시간 잡아먹은 문제

for each에서 for문 가는거 그렇게 어려운 것도 아닌데 중첩이 되어있으니까 좀 헷갈렸던거 같음

 

-------

hint

그냥 dfs구현하고 depth 1에서 5까지 쌓인다면 1을 출력하게 구현하면 됨

-------

Solution

일반 for문

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package Baekjoon.gold;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p13023 {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int isDepthFive = 0;
 
    public void main() throws IOException { // depth 5까지 들어가는지 확인하면됨
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        int a, b;
 
        A = new ArrayList[n];
        visited = new boolean[n];
 
        for (int i = 0; i < n; i++) {
            A[i] = new ArrayList<Integer>();
        }
 
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
 
            A[a].add(b); // 그래도 양방향은 달아야하나보네?
            A[b].add(a);
        }
 
        //구현부
 
        for (int i = 0; i < n; i++) {
            DFS(i, 1);
            if (isDepthFive == 1) {
                break;
            }
        }
 
        System.out.println(isDepthFive);
    }
 
    static void DFS(int n, int depth) {
        if (depth == 5 || isDepthFive == 1) {
            isDepthFive = 1;
            return;
        }
 
        visited[n] = true;
 
        for (int i = 0; i < A[n].size(); i++) {
            if (!visited[A[n].get(i)]) {
                DFS(A[n].get(i), depth + 1);
            }
        }
 
        visited[n] = false;
 
    }
}
 
cs

 

for each문

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package Baekjoon.gold;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p13023 {
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int isDepthFive = 0;
 
    public void main() throws IOException { // depth 5까지 들어가는지 확인하면됨
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        int a, b;
 
        A = new ArrayList[n];
        visited = new boolean[n];
 
        for (int i = 0; i < n; i++) {
            A[i] = new ArrayList<Integer>();
        }
 
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
 
            A[a].add(b); // 그래도 양방향은 달아야하나보네?
            A[b].add(a);
        }
 
        //구현부
 
        for (int i = 0; i < n; i++) {
            DFS(i, 1);
            if (isDepthFive == 1) {
                break;
            }
        }
 
        System.out.println(isDepthFive);
    }
 
    static void DFS(int n, int depth) {
        if (depth == 5) {
            isDepthFive = 1;
            return;
        }
 
        visited[n] = true;
 
        for (int i : A[n]) {
            if (!visited[i]) {
                DFS(i, depth + 1);
            }
        }
        visited[n] = false;
    }
}
 
cs

 

처음엔 구현을 못해서 for each로 했는데

일반 for문 구현하고 백준보니까 속도랑 메모리 측면에서 for문이 더 좋았다

그 이유는 chat GPT씨가 설명해줌 ㅎㅎ

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm' 카테고리의 다른 글

백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
백준 2164번 카드2 자바로 풀어 본 짧은 글  (0) 2023.03.18
24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글  (0) 2023.02.04

+ Recent posts

티스토리툴바