[백준] 사탕 게임 3085번 (🥈실버2)

사이트

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

 

문제

 

분석

정처기 때문에 코딩테스트를 많이 못해서 약 3주만에 다시 시작한다. 

 

일단 문제설명이 너무 부실했다. 

테스트 케이스를 통해 유추해본 결과 

최대 사탕수를 먹을 수 있는 갯수라 해도 한 행 또는 열만 해당하는 것이다.

즉 다시 말해서 한 행 또는 열에 연속된 최대 문자 갯수를 출력하는 것이다!

또한 인접한 두 문자가 서로 다를 때만 바꿔야 된다. 

 

전체적인 구현 방식을 bfs로 활용했다. 

private static void bfs() {
    Queue<int[]> queue = new LinkedList<>();

    queue.add(new int[]{0, 0});

    while (!queue.isEmpty()) {
        int[] poll = queue.poll();
        int sX = poll[0];
        int sY = poll[1];

        for (int i = 0; i < 2; i++) {
            int nX = sX + dx[i];
            int nY = sY + dy[i];

            if (nX >= 0 && nX < n && nY >= 0 && nY < n) {
                if (arr[nX][nY] != arr[sX][sY]) {
                    char temp = arr[nX][nY];
                    arr[nX][nY] = arr[sX][sY];
                    arr[sX][sY] = temp;

                    swap();

                    char temp1 = arr[sX][sY];
                    arr[sX][sY] = arr[nX][nY];
                    arr[nX][nY] = temp1;

                    if (max == n) {
                        return;
                    }
                }
                if (!visit[nX][nY]) {
                    queue.add(new int[]{nX, nY});
                }
                visit[nX][nY] = true;

            }
        }

    }
}

bfs() 함수의 전체적인 코드이다. 차근씩 분석해보자 

if (nX >= 0 && nX < n && nY >= 0 && nY < n) {
    if (arr[nX][nY] != arr[sX][sY]) {
        char temp = arr[nX][nY];
        arr[nX][nY] = arr[sX][sY];
        arr[sX][sY] = temp;

        swap();

        char temp1 = arr[sX][sY];
        arr[sX][sY] = arr[nX][nY];
        arr[nX][nY] = temp1;

        if (max == n) {
            return;
        }
    }
    if (!visit[nX][nY]) {
        queue.add(new int[]{nX, nY});
    }
    visit[nX][nY] = true;

}

여기서 부터 보면 된다. 

일단 이전 값을 더한 nX와 nY가 범위에 맞는지 먼저 체크를 한다. 

if (arr[nX][nY] != arr[sX][sY])

그 후 이전 값과 더한 값이 일치하지 않을때 즉 다른 사탕이므로 바꿔주기 위해 if문으로 들어온다. 

char temp = arr[nX][nY];
arr[nX][nY] = arr[sX][sY];
arr[sX][sY] = temp;

swap();

char temp1 = arr[sX][sY];
arr[sX][sY] = arr[nX][nY];
arr[nX][nY] = temp1;

 

위 코드에서 문자 위치들을 서로 바꾸고 바로 swap() 함수로 간다! 

 private static void swap() {
        int max_w = 0;
        int max_1w = 0;

        for (int i = 0; i < n; i++) {
            int max_1 = 1;
            for (int j = 0; j < n - 1; j++) {
                if (arr[i][j] == arr[i][j + 1]) {
                    max_1++;
                    max_1w = Math.max(max_1w, max_1);
                } else {
                    max_1w = Math.max(max_1w, max_1);
                    max_1 = 1;
                }
            }

            max_w = Math.max(max_1w, max_w);
        }


        int max_h = 0;
        int max_2h = 0;
        for (int i = 0; i < n; i++) {
            int max_2 = 1;
            for (int j = 0; j < n - 1; j++) {
                if (arr[j][i] == arr[j + 1][i]) {
                    max_2++;
                    max_2h = Math.max(max_2h, max_2);
                } else {
                    max_2h = Math.max(max_2h, max_2);
                    max_2 = 1;
                }
            }
            max_h = Math.max(max_2h, max_h);
        }
        max = Math.max(max, Math.max(max_h, max_w));
    }
}

 

swap()함수 구조이다. 

바꾼 문자들을 토대로 각 행 및 열을 싹다 다 비교해서 연속적으로 최대 문자 갯수를 max에 최종적으로 저장한다. 

 

char temp1 = arr[sX][sY];
        arr[sX][sY] = arr[nX][nY];
        arr[nX][nY] = temp1;

        if (max == n) {
            return;
        }
    }
    if (!visit[nX][nY]) {
        queue.add(new int[]{nX, nY});
    }
    visit[nX][nY] = true;

}

 그 후 다시 문자들을 원위치로 저장하고 

시간 초과를 막기 위해서 n이 max랑 같을때 바로 return 하게 했다. 왜냐하면 연속된 문자열 최대 갯수는 n이기 때문이다. 

 

static int[] dx = {1, 0};
static int[] dy = {0, 1};

if (!visit[nX][nY]) {
        queue.add(new int[]{nX, nY});
    }
    visit[nX][nY] = true;

}

또한 이전과 다르게 dx dy를 10 // 01 로 구성했다. 

왜냐하면 시작점이 고정되어 있고 아래, 오른쪽으로 이동하면서 문자를 비교하기 위함이다. 

또한 큐에서 중복 값을 방지하기 위해  boolean 배열인 visit를 활용하여 위와 같이 방지를 하였다. 

 

swap();
bfs();
if (max == 0) {
    System.out.println(n);
} else {
    System.out.println(max);
}

맨처음 시작점 main 함수에서 다음과 같이 코드를 작성하였다. 

max==0 일때는 모든 문자가 같다는 의미로 n을 출력하게 하였고 

swap()를 먼저 출력한 이유는 맨 처음 배열을 최대값을 얻기 위함이다. 

 

전체코드

package bra;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.LinkedList;
import java.util.Queue;

public class Bra3085 {

    static int n;
    static int max = 0;
    static char[][] arr;

    static boolean[][] visit;

    static int[] dx = {1, 0};
    static int[] dy = {0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new char[n][n];
        visit = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            String message = br.readLine();
            for (int j = 0; j < n; j++) {
                arr[i][j] = message.charAt(j);
            }
        }

        swap();
        bfs();
        if (max == 0) {
            System.out.println(n);
        } else {
            System.out.println(max);
        }
    }

    private static void bfs() {
        Queue<int[]> queue = new LinkedList<>();

        queue.add(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int sX = poll[0];
            int sY = poll[1];

            for (int i = 0; i < 2; i++) {
                int nX = sX + dx[i];
                int nY = sY + dy[i];

                if (nX >= 0 && nX < n && nY >= 0 && nY < n) {
                    if (arr[nX][nY] != arr[sX][sY]) {
                        char temp = arr[nX][nY];
                        arr[nX][nY] = arr[sX][sY];
                        arr[sX][sY] = temp;

                        swap();

                        char temp1 = arr[sX][sY];
                        arr[sX][sY] = arr[nX][nY];
                        arr[nX][nY] = temp1;

                        if (max == n) {
                            return;
                        }
                    }
                    if (!visit[nX][nY]) {
                        queue.add(new int[]{nX, nY});
                    }
                    visit[nX][nY] = true;

                }
            }

        }
    }

    private static void swap() {
        int max_w = 0;
        int max_1w = 0;

        for (int i = 0; i < n; i++) {
            int max_1 = 1;
            for (int j = 0; j < n - 1; j++) {
                if (arr[i][j] == arr[i][j + 1]) {
                    max_1++;
                    max_1w = Math.max(max_1w, max_1);
                } else {
                    max_1w = Math.max(max_1w, max_1);
                    max_1 = 1;
                }
            }

            max_w = Math.max(max_1w, max_w);
        }


        int max_h = 0;
        int max_2h = 0;
        for (int i = 0; i < n; i++) {
            int max_2 = 1;
            for (int j = 0; j < n - 1; j++) {
                if (arr[j][i] == arr[j + 1][i]) {
                    max_2++;
                    max_2h = Math.max(max_2h, max_2);
                } else {
                    max_2h = Math.max(max_2h, max_2);
                    max_2 = 1;
                }
            }
            max_h = Math.max(max_2h, max_h);
        }
        max = Math.max(max, Math.max(max_h, max_w));
    }
}

 

결과

 

느낀점

시간초과 떠서 중복 큐를 제거 하였고 첫 배열 검사를 안해줘서 조금 애먹었다.... 

문제 설명도 부족하고.... 

열심히 해보자 2시간 걸린문제였다.