반응형

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

2310번 어드벤처 게임

 

2310번: 어드벤처 게임

입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타

www.acmicpc.net

Comment
문제 이해하는데 한참 걸렸던 문제 생각보다 구현은 엄청 어렵지는 않았다.
문제 이해를 돕자면 각 줄이 1, 2, 3, 4번 방으로 쭉 나열되는 것이고, E,L,T의 상태를 가진 방 으로 생각하면 편할 것 같다.
다들 쉽게 이해하겠지만 저는 좀 힘들었습니다..

Hint

  • 기본적인 방의 번호와 상태를 담은 mapList
  • 방문을 확인할 배열 visited
  • n번방에 도달했는지 확인하는 success

Solution
문제 이해하기까지도 오래 걸리고, 아직 문해력이 부족한건지 모호했던 부분이 많았던 문제 그래도 직접 해결해서 뿌듯하다

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
package Baekjoon.gold;
 
import java.io.*;
import java.util.*;
 
 
/**
 * 3
 * E 0 2 0
 * L 10 3 0
 * T 15 1 2 0
 *
 * E 빈방, L 레프리콘, T 트롤
 * 두번째 0, 10, 15 금액
 * 레프리콘은 10원 기준
 * 트롤은 15원 기준
 *
 * 1번방 출발 빈방시작
 * 이후의 값은 다 다른 방과 이어지는 번호
 *
 * 처음 모험가가 시작하는 방 번호 1
 *
 * 연결리스트로 추가하기
 *
 */
public class p2310 {
 
    static ArrayList<Room> mapList;
    static boolean[] visited;
    static int n;
    static StringBuilder sb = new StringBuilder();
    static boolean flag;
    static boolean success;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
        while(n > 0){
            mapList = new ArrayList<>();
            visited = new boolean[n+1];
            int myMoney = 0;
            flag = true;
            success = false;
            //0번방의 필요없는 데이터 주입
            mapList.add(new Room(-1,"NOTHING",-1));
            //
 
            for(int roomNumber = 1; roomNumber <= n; roomNumber++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                Room roomInit = new Room(
                        roomNumber,
                        st.nextToken(),
                        Integer.parseInt(st.nextToken())
                );
 
                int inputNum = Integer.parseInt(st.nextToken());
                while(inputNum > 0){
                    roomInit.roomNumberAdd(inputNum);
                    inputNum = Integer.parseInt(st.nextToken());
                }
                mapList.add(roomInit);
            }
 
            dfs(1, myMoney);
 
            if(!success){
                sb.append("No").append("\n");
            }else{
                sb.append("Yes").append("\n");
            }
            n = Integer.parseInt(br.readLine());
        }
 
        System.out.println(sb);
 
    }
 
    static void dfs(int roomNum, int myMoney){
        if(success){
            return;
        }
        visited[roomNum] = true;
 
        Room nowRoom = mapList.get(roomNum);
        myMoney = nowRoom.visitRoomEvent(myMoney);
        if(myMoney >= 0){
            if(n == roomNum){
                success = true;
                return;
            }
            for(int roomNumber : nowRoom.getLinkedRoomList()){
                if(!visited[roomNumber]) {
                    dfs(roomNumber, myMoney);
                }
            }
        }else{
            visited[roomNum] = false;
            return;
        }
    }
 
    private static class Room{
        int roomNum;
        String roomType;
        int roomMoney;
        final ArrayList<Integer> roomList;
        Room(int roomNumber, String type, int money){
            this.roomMoney = money;
            this.roomNum = roomNumber;
            this.roomList = new ArrayList<>();
            this.roomType = type;
        }
 
        void roomNumberAdd(int number){
            roomList.add(number);
        }
 
        ArrayList<Integer> getLinkedRoomList(){
            return roomList;
        }
 
        int visitRoomEvent(int money){
            if(roomType.equals("L")){
                if(money < this.roomMoney){
                    return this.roomMoney;
                }
            }
            if(roomType.equals("T")){
                if(money < this.roomMoney){
                    return -1;
                }
                money -= roomMoney;
                return money;
            }
            return money;
        }
    }
}
cs

 

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

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

백준 29812번 아니 이게 왜 안돼 자바로 풀어 본 짧은 글  (0) 2023.12.01
백준 11559번 Puyo Puyo 자바로 풀어 본 짧은 글  (0) 2023.11.30
백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글  (0) 2023.09.15
백준 1680번 쓰레기 수거 자바로 풀어 본 짧은 글  (0) 2023.09.07
반응형

2644번 촌수 계산

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

 

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어

www.acmicpc.net

Comment

 DFS, BFS를  첫 입문할 때 하기 좋은 그래프 문제이다. 해당 문제는 DFS적으로 접근하면 Depth를 잘 활용할 수 있었는데, BFS를 활용해서 풀어볼 때 문제가 생겼었다. 직면했던 문제는 BFS에서는 Depth를 어떤 기준으로 체크할 수 있을까? 라는 고민을 많이 하게 한 문제였다.

hint

DFS, BFS 두가지 방법 모두 풀린다.

하지만 체감 난이도는 BFS가 더 어려웠던 것 같다.

Solution

  • DFS

재귀호출할 때 매개변수를 통해서 해당 깊이를 더해가며 풀어보니 잘 해결되었다.

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
import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean[] check;
    static ArrayList<Integer>[] al;
    static int n, m, start, target;
    static boolean flag;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
 
        m = Integer.parseInt(br.readLine());
 
        al = new ArrayList[n + 1];
        check = new boolean[n + 1];
 
        for (int i = 0; i < n + 1; i++) {
            al[i] = new ArrayList<>();
        }
 
        int x, y;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
 
            al[x].add(y);
            al[y].add(x);
        }
        check[start] = true;
        dfs(start, 0);
        if (!flag) {
            System.out.println(-1);
        }
 
    }
 
    static void dfs(int n, int count) { //7 3
        if (n == target) { //도착하면 flag 변경 후 종료
            flag = true;
            System.out.println(count);
            return;
        } else if (flag) { //이미 찾았으면 더이상 dfs를 돌 필요 없음
            return;
        } else {
            for (int a : al[n]) {
                if (!check[a]) {
                    check[a] = true;
                    dfs(a, count + 1);
                }
            }
        }
    }
}
cs
  • BFS

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
71
72
73
import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean[] check;
    static ArrayList<Integer>[] al;
    static int n, m, start, target;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
 
        m = Integer.parseInt(br.readLine());
 
        al = new ArrayList[n + 1];
        check = new boolean[n + 1];
 
        for (int i = 0; i < n + 1; i++) {
            al[i] = new ArrayList<>();
        }
 
        int x, y;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
 
            al[x].add(y);
            al[y].add(x);
        }
 
        bfs(start, target);
 
    }
 
    static void bfs(int start, int target) { // null을 활용해서 깊이 구분자를 생성
        int count = 0;
 
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        q.add(null);
        check[start] = true;
 
        while (!q.isEmpty()) {
            Integer now = q.poll();//null을 활용하기 위해 Integer로 
 
            if(now == null) {//null을 만날 때마다 깊이가 깊어짐 count++
                if(!q.isEmpty()) {
                    q.add(null);
                    count++;
                }
            }else {
                for (int y : al[now]) {
                    if (!check[y]) {
                        check[y] = true;
                        if (y == target) { // bfs깊이에 따라서 체크 후 해당 깊이 출력
                            System.out.println(count + 1);
                            return;
                        }
                        q.add(y);
                    }
                }
            }
        }
        System.out.println(-1);
    }
}
cs

내가 만질 때는 null을 Queue에 넣어서 구분자로 생각하고 null을 만날 때마다 count가 1씩 증가하도록 구현했었는데, 좀 더 직관적인 방법이 좋았을거라 생각했고, 스터디를 진행하는 다른 사람이 푼 것을 봤을 때 distance라는 배열을 만들어서 해당 값을 누적되게 구현했는데 더 좋은 방법 같았다.

어쨌든 그래프에서 DFS, BFS를 둘 다 사용해보기에 좋은 문제였던 것 같다!

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

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

백준 1417번 국회의원 선거 자바로 풀어 본 짧은 글  (0) 2023.08.17
백준 골드5 달성!  (0) 2023.08.11
백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25
백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
알고리즘 근황  (0) 2023.07.23
반응형

2023번 신기한 소수

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

 

2023번: 신기한 소수

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수

www.acmicpc.net

Comment

 처음에는 소수판별이기 때문에 이전에 배워뒀던 에라토스테네스의 체를 사용하려고 했다. 하지만 이 문제는 메모리제한이 4MB에 N의 범위가 8 즉 최대 10,000,000 천만의 범위이기 때문에 자바의 데이터 최소단위 byte - boolean크기: 1byte로 지정되었을 때 에토체의 boolean배열만 어림잡아 100mb가 넘게된다 때문에 기각.

일반 소수판별 메서드를 생성해서 처리했다.

hint

DFS, 소수판별을 해야한다

Solution

 최종적으로 가지치기 등등 다양하게 하니까 속도가 좀 빨라졌다. 1,3,5,7,9가 아닌 0~10까지 돌렸을 때는 속도가 좀 느렸었다.

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
import java.io.*;
import java.util.*;
 
 
public class Main {
    static int[] firstPrime = {2, 3, 5, 7};
    static int n;
    static ArrayList<Integer> magicPrime = new ArrayList<>();//신기한 소수를 담을 리스트
 
//    static int count = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
//        int jari = (int)Math.pow(10, n); // 끝자리까지보기
 
        //4메가면 에토체가 가능한가?
        // 1000000 백만에 1M 4백만이면 끝나는데 안된다.
        //나중에 에토체로 구현되나만 체크해보면 재밌을듯
 
        //한자릿수는 배열을만들자 이걸 가지고 시작
        //이걸로 조합을 다하면 그건 브루트포스아닌가?
        //그래서 DFS느낌으로 가는건가?
 
        //슈도흐름을 생각해보자.
        //1. 한자릿수 prime등록 이후는 전부됨......
        //2. 두번째부터 그 수를 붙여서 prime인지 확인 (n을 입력받은 중단점까지)
        //2_1. DFS를 활용, String에 붙여서 다음 DFS로 이동
        //2_2. 백트래킹도 무조건 넣어야할듯? 한 Depth에서 같은 소수를 여러번 반복해야함
        //3. 중단점을 찾았으면 그 수를 리스트에 추가
        //4. 리스트에 추가된거 출력!
 
        for (int i = 0; i < firstPrime.length; i++) {
            dfs(String.valueOf(firstPrime[i]), 1);
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < magicPrime.size(); i++) {
            if(i == magicPrime.size()-1){
                sb.append(magicPrime.get(i));
            }else {
                sb.append(magicPrime.get(i) + "\n");
            }
        }
        System.out.print(sb);
 
    }
 
    static void dfs(String s, int count) {
        if (count == n && isPrime(Integer.valueOf(s))) {//중단점
            magicPrime.add(Integer.valueOf(s));
        }
        if (isPrime(Integer.valueOf(s))) {
            for (int i = 1; i < 10; i += 2) {
                    dfs(s.concat(String.valueOf(i)), count + 1);
            }
        }
    }
 
    static boolean isPrime(int isPrimeNum) {
        for (int i = 2; i <= (int) Math.sqrt(isPrimeNum); i++) {
            if (isPrimeNum % i == 0) {
                return false;
            }
        }
        return true;
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

백준 골드5 달성!  (0) 2023.08.11
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
알고리즘 근황  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
반응형

2583번 영역 구하기

문제 링크 : https://www.acmicpc.net/problem/2583

 

2583번: 영역 구하기

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오

www.acmicpc.net

 

Comment

DFS공부를 시작하면서 만나게 된 문제다. 처음 떠올랐던 아이디어는 이전에 풀었던 색종이 문제처럼 먼저 구현해둔 맵 배열에 칠하고 나머지 갈라진 부분을 DFS로 채워나가자고 생각하고 접근했다.

hint

  • Map을 칠하고 구분된 빈곳을 돌 때마다 count를 해주면 될듯?

Solution

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
import java.io.*;
import java.util.*;
 
public class Main {
 
    static boolean map[][];
    static int count = 0;
 
    static int n, m, k;
 
    static int rectangleSize = 0;
    static ArrayList<Integer> rectangleSizeList = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
 
        map = new boolean[m][n];
 
        for(int i = 0; i < k; i++){
            st = new StringTokenizer(br.readLine());
            drawRectangle(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())
                    ,Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
        }
 
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(!map[i][j]){
                    count++;
                    dfs(i, j);
                    rectangleSizeList.add(rectangleSize);
                    rectangleSize = 0;
                }
            }
        }
        Collections.sort(rectangleSizeList);
        StringBuilder sb = new StringBuilder();
        sb.append(count).append("\n");
 
        for(int i = 0; i < rectangleSizeList.size(); i++){
            sb.append(rectangleSizeList.get(i) + " ");
        }
        System.out.println(sb);
    }
 
    static void dfs(int x, int y){
        if(x >= 0 && y >= 0 && x < m && y < n) {
            if (!map[x][y]) {
                map[x][y] = true;
                rectangleSize++;
                dfs(x + 1, y);
                dfs(x - 1, y);
                dfs(x, y + 1);
                dfs(x, y - 1);
            }
        }
    }
    static void drawRectangle(int x1, int y1, int x2, int y2){
        for(int i = y1; i < y2; i++) {
            Arrays.fill(map[i], x1, x2, true);
        }
    }
}
cs

 

Arrays.fill 메서드를 활용해보고 싶어서 사용했고, fill메서드를 안쓰고 각 좌표별로 true체크를 한 후에 칠했으면 조금 더 효율이 좋을 것 같다.

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

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

백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글  (0) 2023.08.03
백준 2023번 신기한 소수 자바로 풀어 본 짧은 글  (0) 2023.07.25
알고리즘 근황  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
반응형

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

티스토리툴바