반응형

백준 11559 Puyo Puyo

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

 

11559번: Puyo Puyo

총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.

www.acmicpc.net

Comment
기본적인 탐색 + 구현 시뮬레이션 문제
확실히 구현이 들어가니까 실수하는게 생기고 실수했을 때 원인찾기가 어렵다. 지금은 디버깅으로 가능하지만 코테에서는 신경을 많이 써서 해야할 듯?

Hint

  • 기본적인 BFS이동을 담을 movePoint
  • 방문체크 visited
  • 게임판 puyoMap
  • 연쇄횟수
  • 매 라운드가 있어야하기에 puyoClear(boolean)
  • 연쇄가 발생했을 때 뿌요를 지울 ArrayList

아직 깔끔하게 구현은 못하겠지만 어느걸 써야할지는 계속 생각하며 풀어야 함

Solution
1. 탐색하고 탐색된 좌표 저장
2. 탐색된 좌표가 4개 이상일 때 puyoClear = true, 실제로 지울 clearPuyoMap List에 추가
3. clearPuyoMap 기반으로 뿌요들을 아래로 내려줌
4. 한번 지워진 상태(puyoClear == true)라면 1~3 반복

큰 흐름은 위의 순서로 진행된다.
값 초기화 잘 신경써서 해주면 크게 어렵지는 않다.

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
package Baekjoon.gold;
 
import java.io.*;
import java.util.*;
 
public class p11559 {
    static final int[][] movePoint = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static boolean[][] visited = new boolean[12][6];
    static char[][] puyoMap = new char[12][6];
    static int count = 0;
    static int n = 12;
    static boolean puyoClear = false;
    static ArrayList<int[]> accumulatePuyoMap = new ArrayList<>();
    static ArrayList<int[]> clearPuyoMap = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < n; i++) {
            puyoMap[i] = br.readLine().toCharArray();
        }
 
        do {
            puyoClear = false;
            puyoGame();
            if (puyoClear) {
                count++;
                puyoMove();
            }
            clearPuyoMap.clear();
            visited = new boolean[12][6];
        } while (puyoClear);
        System.out.println(count);
 
    }
 
    static void puyoGame() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 6; j++) {
                if (puyoMap[i][j] != '.' && !visited[i][j]) {
                    bfs(i, j, puyoMap[i][j]);
                }
            }
        }
    }
 
    static void bfs(int x, int y, char puyoColor) {
        Queue<int[]> q = new LinkedList<>();
        visited[x][y] = true;
        q.add(new int[]{x, y});
        accumulatePuyoMap.clear();
        accumulatePuyoMap.add(new int[]{x, y});
 
        while (!q.isEmpty()) {
            int[] nowXY = q.poll();
            for (int[] moveXY : movePoint) {
                int nowX = nowXY[0] + moveXY[0];
                int nowY = nowXY[1] + moveXY[1];
                if (nowX >= 0 && nowY >= 0 &&
                        nowX < 12 && nowY < 6 &&
                        puyoColor == puyoMap[nowX][nowY] &&
                        !visited[nowX][nowY]) {
                    visited[nowX][nowY] = true;
                    q.add(new int[]{nowX, nowY});
                    accumulatePuyoMap.add(new int[]{nowX, nowY});
                }
            }
        }
        if (accumulatePuyoMap.size() >= 4) {
            puyoClear = true;
            clearPuyoMap.addAll(accumulatePuyoMap);
        }
    }
 
    static void puyoMove() {
        //4개 이상인 뿌요를 .으로 초기화
        for (int[] clearXY : clearPuyoMap) {
            puyoMap[clearXY[0]][clearXY[1]] = '.';
        }
 
        //.을 탐색하며 뿌요를 위로 올려줌
        int[] firstDotPlace = new int[2];
        for (int i = 0; i < 6; i++) {
            boolean firstDotCheck = false;
            Queue<Character> upMovePuyo = new LinkedList<>();
            for (int j = 11; j >= 0; j--) {
                if (puyoMap[j][i] == '.') {
                    if (firstDotCheck) {
                        continue;
                    }
                    firstDotPlace[0] = j;
                    firstDotPlace[1] = i;
                    firstDotCheck = true;
                } else if (firstDotCheck) {
                    upMovePuyo.add(puyoMap[j][i]);
                    puyoMap[j][i] = '.';
                }
            }
            int nowX = firstDotPlace[0];
            int nowY = firstDotPlace[1];
            while (!upMovePuyo.isEmpty()) {
                puyoMap[nowX][nowY] = upMovePuyo.poll();
                nowX--;
            }
        }
    }
}
 
cs

 

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

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

백준 16401 과자 나눠주기 자바로 풀어 본 짧은 글  (0) 2023.12.02
백준 29812번 아니 이게 왜 안돼 자바로 풀어 본 짧은 글  (0) 2023.12.01
백준 2310번 어드벤처 게임 자바로 풀어 본 짧은 글  (0) 2023.11.28
백준 12755번 수면 장애 자바로 풀어 본 짧은 글  (0) 2023.11.21
백준 14494번 다이나믹이 뭐예요? 자바로 풀어 본 짧은 글  (0) 2023.09.15
반응형

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
반응형

24444번 너비 우선 탐색 1

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

 

24444번: 알고리즘 수업 - 너비 우선 탐색 1

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방

www.acmicpc.net

 

이번엔 BFS... DFS 보다 습득하는데 더 오래 걸린 듯 하다

그나마 이번 문제 풀면서 범위설정이나 조건이나 여러가지로 감을 좀 잡은듯

 

------

hint

해당 번호가 몇번째 순서로 도달했는지 저장하는 배열이 따로 필요

------

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
 
    static boolean[] isVisit;
    static ArrayList<Integer>[] a;
 
    public static void main(String[] args) throws IOException {
        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 r = Integer.parseInt(st.nextToken());
 
        int u, v;
 
        isVisit = new boolean[n+1];
        a = new ArrayList[n+1];
 
        for(int i = 1; i < n + 1; i++){
            a[i] = new ArrayList<Integer>();
        }
 
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
 
            a[u].add(v);
            a[v].add(u);
        }
 
        for(int i = 1; i < n + 1; i++){
            if(!a[i].isEmpty()) {
                Collections.sort(a[i]);
            }
        }
 
        BFS(r, n, m);
 
    }
 
    static void BFS(int r, int n, int m){ // r이 1이라고 가정했을 때
        Queue<Integer> queue = new LinkedList<>();
 
        int temp;
        int[] count = new int[n+1];
        int countNum = 1;
 
        isVisit[r] = true;
        count[r] = countNum++;
        queue.offer(r);
 
        while(!queue.isEmpty()){
            temp = queue.poll();
            for(int i = 0; i < a[temp].size(); i++) {
                if (!isVisit[a[temp].get(i)]) {//방문하지 않았을 때 실행
                    isVisit[a[temp].get(i)] = true;
                    count[a[temp].get(i)] = countNum++;
                    queue.offer(a[temp].get(i));
                }
            }
        }
 
        for(int i = 1; i < n + 1; i++){
            System.out.println(count[i]);
        }
    }
}
 
cs

 

실행시간 - 1996ms

너무 길어서 최적화좀 해주고싶은데.... BufferedReader말고는 상상이 안됨

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

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

백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22
백준 11004번 K번째 수 자바로 풀어 본 짧은 글  (0) 2023.03.25
백준 2164번 카드2 자바로 풀어 본 짧은 글  (0) 2023.03.18

+ Recent posts

티스토리툴바