반응형

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

11822번 Document

바로 한글변환...

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

 

11822번: Document

In the first example, the document must be signed by two officials — the first one accept documents on Mondays, Wednesdays and Fridays, and the second one — on Mondays and Thursdays. The fastest way to sign the document is one of the following: you s

www.acmicpc.net

이 문제를 처음에 이해하기로는 그냥 어느 공무원이든 모두 일처리를 한번씩만 하면 되는 것으로 착각하고 풀었는데, 접근방식이 틀렸었다.

-----

hint

3명의 공무원이 있다면 첫번째 공무원부터 부터 계단식으로 서류통과를 하는 방식이 맞는 방식이다.

입력케이스 하나를 예로 들었을 때

2
0 1 0 0 1
1 1 0 0 0

각각 배열로 선언을 했다 쳤을 때 두번째 줄 a배열, 세번째 줄 b배열로 치면

a[1] 인덱스에서 1을 발견하고 카운트, 이후 b배열로 이동해서 b[2] -> b[3] -> b[4] ->b[0] 으로 이동을 해서 1을 발견한 b[1]

자리에서 멈춘다 그렇다면 이미 한 주의 사이클이 돌았으니 5일 +2일 + 두번째 주의 1일 해서 8이 나오게 된다

-----

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
import java.util.*;
import java.io.*;
 
public class Main {
    static int count = 0;
    static int length = 0;
    //static boolean bool[] = new boolean[5];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int n = Integer.parseInt(br.readLine());
        int[][] al = new int[n][5];
 
 
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                al[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        length = n;
        goRepeat(al, 0);
    }
 
    static void goRepeat(int[][] a, int n) {
        if (n == length) {
            if (count % 5 == 0 && count / 5 > 0) {
                System.out.println(count + ((count / 5 - 1) * 2));
                return;
            } else {
                System.out.println(count + (count / 5 * 2));//5일 지날때마다 +2
                return;
            }
        }
        go(a[n], count % 5);
        n++;
        goRepeat(a, n);
 
 
        return;
    }
 
    static void go(int a[], int index) {
        for (int i = 0; i < 5; i++) {
            count++;
 
            if (a[index] == 1) {
                return;
            }
            index = (index + 1) % 5;
        }
 
    }
 
}
cs

실행시간 76ms 

처음엔 배열로 풀려고 하다가 재귀함수를 학습하고싶은 마음에 재귀함수를 통해서 풀어봤다.

진짜 별거아닌 코드같은데 놀랍게도 이틀중 5시간은 써가면서 겨우 구현한 것 같다....

재귀 구현 너무 어렵...

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

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

백준 2583번 영역 구하기 자바로 풀어 본 짧은 글  (0) 2023.07.23
알고리즘 근황  (0) 2023.07.23
백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
반응형

p21771 가희야 거기서 자는 거 아니야

처음 접근방법은 G의 각 꼭짓점 별로 좌표를 추적해서 좌우에 P가 있는지 탐색해보는 방식으로 접근했었는데, 정확한 이유는 모르겠지만 실패했다.

그래서 생각해 본 방법이 P의 넓이를 구하고 P의 갯수를 카운트했을 때 넓이가 안맞으면  가희가 베개를 사용하고 있는 것으로 판단하기로 해보고 문제를 풀어봤다.

hint

----

P의 갯수를 활용하는 것이 핵심

----

Solution

실행시간 - 124ms

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
import java.util.*;
import java.io.*;
 
class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int gr = Integer.parseInt(st.nextToken());
        int gc = Integer.parseInt(st.nextToken());
        int pr = Integer.parseInt(st.nextToken());
        int pc = Integer.parseInt(st.nextToken());
        
        char[][] map = new char[r][c];
        
        for(int i = 0; i < r; i++){
            map[i] = br.readLine().toCharArray();
        }
        
        int n = pr * pc; // 60
        int count = 0;
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(map[i][j] == 'P'){
                    count++;
                }
            }
        }
        
        if(count == n){
            System.out.println(0);
        }else{
            System.out.println(1);
        }
        
        
        
    }
    
    
}
cs

 

다음에 기회가 된다면 각 꼭짓점 별로 판단하는 방식을 채용해보고 싶다... 정말 최고의 최적화일거같은데 반례가 어느걸까 궁금하다

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

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

알고리즘 근황  (0) 2023.07.23
백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
백준 13717 포켓몬Go 자바로 풀어 본 짧은 글  (0) 2023.05.25
백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
반응형

13717번 포켓몬Go

내용은 구현이 익숙한 사람들은 효율을 생각 안하면 쉽게 구현할만한 문제같다.

위의 테스트케이스 기준으로 설명을 하자면.

4마리의 포켓몬을 입력받는데, 각 마리마다 입력받는 값은 Caterpie라는 문자열, 레벨업에 필요한 사탕갯수(12), Caterpie에게 투자할 수 있는 사탕의 갯수이다. 1레벨업을 할 때마다 2개의 사탕을 돌려받는다.

 ----

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
import java.util.*;
import java.io.*;
 
class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //pokemon
        //levelupCandy
        //haveCandy
        String[] pokemon = new String[n];
        int[] levelupCandy = new int[n];
        int[] haveCandy = new int[n];
        
        for(int i = 0; i < n; i++){
            pokemon[i] = br.readLine();
            st = new StringTokenizer(br.readLine());
            levelupCandy[i] = Integer.parseInt(st.nextToken());
            haveCandy[i] = Integer.parseInt(st.nextToken());
        }
        //Caterpie
        //12
        //33
        
        int count = 0;
        int tempCount = 0;
        int index = 0;
        int maxCount = 0;
        for(int i = 0; i < n; i++){
            while(haveCandy[i] >= levelupCandy[i]){
                haveCandy[i] -= levelupCandy[i] - 2;
                tempCount++;
            }
            if(maxCount < tempCount){
                maxCount = tempCount;
                index = i;
            }
            count += tempCount;
            tempCount = 0;
        }
        System.out.println(count);
        System.out.println(pokemon[index]);
    }
}
cs

실행시간 - 124ms

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

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

백준 11822번 Document 자바로 풀어 본 짧은 글  (0) 2023.06.08
백준 21771 가희야 거기서 자는 거 아니야 자바로 풀어 본 짧은 글  (0) 2023.05.31
백준 1418 K-세준수 자바로 풀어 본 짧은 글  (0) 2023.05.24
백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글  (0) 2023.04.30
백준 13023번 ABCDE 자바로 풀어 본 짧은 글  (0) 2023.04.22

+ Recent posts

티스토리툴바