[코드트리] 5 - 구현/시뮬레이션 및 해결 전략 총정리

시뮬레이션 

구현 및 시뮬레이션은 어느 문제를 풀던 기반이 되는 일종의 헬스같은 거라 주기적으로 풀어줘야 한다. 보통 구현 문제는 지문이 굉장히 길고 친절한 문제라면 그림을 같이 준다. 따라서 한 번에 요구사항을 가려내는게 실전에서 시간 관리에 있어서 경쟁자에 비해 유리할 것이다. 또한, 구현/시뮬레이션 문제는 다른 문제를 풀기 위한 받침돌 역할이 되기 때문에 아이디어는 게을러도 개개인의 능력에 따라 떠올릴 수 있지만 구현력은 성실하게 꾸준히 푸는 게 답인 것 같다.

 

이러한 유형의 문제는 패턴을 발견하던지 상태를 추출해서 압축하던지 아니면 템플릿으로 빠르게 풀어야 한다. 자신만의 네이밍 규칙, 함수 추상화 방식 등의 구조적인 룰을 갖추는 것이 좋고 아직 확립되지 않았다면 깨끗하게 정리된 다른 사람의 풀이를 보고 배우는 것이 좋다고 생각한다. 따라서, 문제별 사고의 흐름과 풀이, 구현상 팁 등을 서술하겠다.

주로 해결 전략을 다루는 Trail 2 - chapter 9과 여러 웰논 구현 문제들이 있는 Trail 4 - chaper 1을 동시에 다룬다. 

이번 주차 미션은 특정 알고리즘에 대한 개념서를 쓰는 것인데 사실상 처음부터 이런식으로 개념 정리 + 문제 풀이 및 팁 + 최적화를 계속 써 왔기 때문에 다른 주제에 관해서는 아래 링크를 참고하길 바란다.

 

완전탐색, 누적합, DFS -> https://study-fridge.tistory.com/538

트리, binary 트리 -> https://study-fridge.tistory.com/542

DP, LIS, 부분합 DP -> https://study-fridge.tistory.com/544

DP on Tree, Lowest Common Ancesstor(LCA) -> https://study-fridge.tistory.com/545

---

문제 - 전부 겹치는 선분 2 (최적화)

https://www.codetree.ai/ko/trails/complete/curated-cards/test-overlapping-line-segments-2/description

전부 겹치는 선분 2 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static int[][] A;

    public static void main(String[] args) throws IOException{
        N = read();
        A = new int[N][2];
        for(int i = 0; i<N; i++){
            A[i] = new int[]{read(), read()};
        }

        // pml = [0, i] 까지 봤을때 maxL
        // sml = [i, N-1] 까지 봤을때 maxl
        int[] pMaxL = new int[N];
        pMaxL[0] = A[0][0];
        for(int i = 1; i<N; i++){
            pMaxL[i] = Math.max(pMaxL[i-1], A[i][0]);
        }

        int[] pMinR = new int[N];
        pMinR[0] = A[0][1];
        for(int i = 1; i<N; i++){
            pMinR[i] = Math.min(pMinR[i-1], A[i][1]);
        }

        int[] sMaxL = new int[N];
        sMaxL[N-1] = A[N-1][0];
        for(int i = N-2; i>=0; i--){
            sMaxL[i] = Math.max(sMaxL[i+1], A[i][0]);
        }

        int[] sMinR = new int[N];
        sMinR[N-1] = A[N-1][1];
        for(int i = N-2; i>=0; i--){
            sMinR[i] = Math.min(sMinR[i+1], A[i][1]);
        }

        int l = -1;
        int r = 101;
        boolean found = false;
        // 제외할 선분 idx = i 
        for(int i= 0; i<N; i++){
            if(i == 0){
                l = sMaxL[1];
                r = sMinR[1];
            }
            else if(i == N-1){
                l = pMaxL[N-2];
                r = pMinR[N-2];
            }
            else{
                l = Math.max(pMaxL[i-1], sMaxL[i+1]);
                r = Math.min(pMinR[i-1], sMinR[i+1]);
            }

            if(l<=r){
                found = true;
                break;
            }
        }

        if(found)
            System.out.print("Yes");
        else
            System.out.print("No");
    }
}

사고의 흐름

N개의 1차원 선분의 시작과 끝이 주어졌을 때, 단 1개의 선분을 제거한 상황에서 나머지 모든 선분이 겹치는 상황이 가능한지?

-> 뺄 선분 i를 하나 잡고 나머지를 L,R 교집합 순차적으로 업데이트해서 연산하기

-> 이렇게 하면 O(N^2) 뭔가 O(N)으로 풀 수 있을 거 같은데

 

N-1개가 겹친다는 말을 다시 해석해보면

어떤 i를 한 개 제거했을 때 남은 구간들의 교집합이 존재한다는 뜻임

-> [0,i-1] + [i+1, N-1] 으로 표현가능

따라서, 하나를 제외한 전체 정보가 필요하므로 Prefix + suffix 패턴을 적용할 수 있음.

 

풀이 : Prefix & Suffix pattern

어떤 N개의 선분에 대한 교집합은 다음과 같이 구한다.

L = 겹치는 구간의 시작점, R = 겹치는 구간의 끝점 라고 정의하면

L과 R은 선분 교집합의 누적 갱신으로 O(1)에 연산할 수 있다.

L = Math.max( 이전의 L 값, 현재 선분의 시작점 )
R = Math.min( 이전의 R 값, 현재 선분의 끝점 )

 

prefix는 처음부터 i까지 구간을 누적해서 미리 전처리하는 것이고 

suffix는 i부터 맨 뒤까지 구간을 누적해서 전처리하는 것이다.

그러면 prefix 2개, suffix 2개 총 4개의 배열이 필요하다.

prefixMaxL[i] = [0, i] 구간 선분들의 시작점 최댓값
prefixMinR[i] = [0, i] 구간 선분들의 끝점 최솟값
suffixMaxL[i] = [i, N-1] 구간 선분들의 시작점 최댓값
suffixMinR[i] = [i, N-1] 구간 선분들의 끝점 최솟값

 

prefix 는 [0, i] 구간의 max나 min 값을 저장하는 배열로 두고

suffix 는 [i, N-1] 구간의 max나 min 값을 저장하는 배열로 두면 겹치는 구간의 L, R 연산을 다음과 같이 표현 가능함.

L = Math.max( prefixMaxL[i-1], suffixMaxL[i+1] )
R = Math.min( prefixMinR[i-1], suffixMinR[i+1] )

-> O(1)에 연산 가능

 

총 시간 복잡도 = O(N) 전처리 + O(N) 검사 = O(N) 

 

스위핑 풀이와의 비교

차분배열 + 누적합 을 활용한 풀이는 X 를 입력값의 범위라고 할 때, 

시간/공간 복잡도는 O(N+X)임

따라서 X가 커지면 좌표 압축 및 이벤트 기반 sweep line이 필요해짐

그에 비해 해당 풀이는 X에 의존적이지 않아 그대로 O(N)

 

---

문제 - 최고의 33위치(2차원 누적합 템플릿)

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-best-place-of-33/description

최고의 33위치 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    public static void main(String[] args) throws IOException{
        int N = read();
        int[][] board = new int[N+1][N+1];
        int[][] psum = new int[N+1][N+1];

        for(int i = 1; i<=N; i++){
            for(int j = 1; j<=N; j++){
                board[i][j] = read();
            }
        }

        for(int i = 1; i<=N; i++){
            for(int j = 1; j<=N; j++){
                psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + board[i][j];
            }
        }

        int cur = psum[3][3];
        int ans = Math.max(0, cur);
        for(int i = 3; i<=N; i++){
            for(int j= 3; j<=N; j++){
                cur = psum[i][j] - psum[i-3][j] - psum[i][j-3] + psum[i-3][j-3];
                ans = Math.max(ans, cur);
            }
        }
        System.out.print(ans);
    }
}

 

---

문제 - 트로미노

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-tromino/solutions

트로미노 해설 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    // 6 3 2 -> 왼쪽위 시작지점 기준 저거대로 더하다가 세개중에 ni,nj가 invalid 하면 continue
    // 세개 다 valid 하면 적힌 숫자 합 ans에 maximize
    static int[][][] block = {{{0,0},{1,0},{1,1}},{{0,0},{0,1},{1,0}},{{0,0},{0,1},{1,1}},{{0,1},{1,0},{1,1}}
                                ,{{0,0},{0,1},{0,2}},{{0,0},{1,0},{2,0}}};
    static int[][] board;
    static int N,M;
    static int ans = -1;

    static void calc(int si, int sj){
        outer:
        for(int i =0 ; i<6; i++){
            int sum = 0;
            for(int k = 0; k<3; k++){
                int ni = si + block[i][k][0];
                int nj = sj + block[i][k][1];
                if(ni < 0 || nj < 0 || ni >= N || nj >= M)
                    continue outer;
                sum += board[ni][nj];
            }
            ans = Math.max(ans, sum);
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        board = new int[N][M];
        for(int i= 0; i<N; i++){
            for(int j = 0; j<M; j++){
                board[i][j] = read();
            }
        }
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                calc(i,j);
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

왼쪽 위를 시작점으로 잡고 가능한 모양을 잡아보면, 여기서는 모두 3칸씩이므로 si,sj 를 시작 좌표하 하면 모든 블록의 칸은 

ni = si + di[block] , nj = sj + dj[block] 으로 나타낼 수 있다. 

따라서 diff 값을 i,j 좌표마다 저장하는 방식으로 나타낸게 block 배열이다. 

가능한 모양을 0과 1로 주석에 그려서 나타내고 여기서는 ㄴ자가 4가지, ㅡ자가 2가지이고 항상 왼쪽 위에서 오른쪽 아래로 보면 된다. 그리고 ㄴ자는 사실 공백까지 포함해서 2*2칸이므로 방향성 의미가 없다. 

 

board가 N * M 인것에 주의하면서 ni, nj의 validation을 수행한다. for 문에 alias를 줘서 세 칸을 계산할때 한 칸이라도 invalid 한 좌표값을 참조한다면 전체를 continue 하는 식으로 진행해 주면 된다.

---

문제 - 금 채굴하기(마름모 탐색)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-gold-mining/description

금 채굴하기 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static int[][] board;
    static int cost;

    static int calc(int si, int sj, int K){
        int sum = 0;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                if(Math.abs(i-si)+Math.abs(j-sj) <= K)
                    sum += board[i][j];
            }
        }
        return sum;
    }


    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        board = new int[N][N];
        for(int i= 0; i<N; i++){
            for(int j = 0; j<N; j++){
                board[i][j] = read();
            }
        }

        int ans = 0;
        
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                for(int k = 0; k<=N; k++){
                    int cost = k*k + (k+1)*(k+1);
                    int cur = calc(i,j,k);
                    if(cur*M >= cost){
                        ans = Math.max(ans, cur);
                    }
                }
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

처음에는 bfs로 다 탐색해서 풀까 생각했는데 뭔가 실수 많이할거같아서 

좌표로 패턴 발견해서 푸는 방법으로 선회함. 

중심점을 0,0이라 하면 크기가 K로 주어진 마름모는 그 안에 들어가는 좌표라면 항상

abs( cur I - center I ) + abs( cur J - center J ) <= K 를 만족함. 

 

따라서 K가 최대 N일때 -> 문제 조건에서 격자 밖을 벗어나도 된다고 했으니 최대 N일것임. 

-> 시간복잡도는 O(N^2 * N * N^2)

-> 마름모 테두리만 세는 식으로 누적해서 해주는 것도 생각은 했는데 그러면 시간복잡도는 줄겠지만 머리터질듯;

---

문제 - 겹쳐지지 않는 두 직사각형

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-non-overlapping-two-rectangles/description

겹쳐지지 않는 두 직사각형 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N, M;
    // 1-based index
    static int[][] board;
    static int[][] psum;

    //a가 왼쪽위 , b가 오른쪽아래라고 가정
    static boolean isOverlap(int sia, int sja, int ra, int ca, int sib, int sjb, int rb, int cb){
        int aTop = sia;
        int aBottom = sia + ra - 1;
        int aLeft = sja;
        int aRight = sja + ca - 1;

        int bTop = sib;
        int bBottom = sib + rb - 1;
        int bLeft = sjb;
        int bRight = sjb + cb - 1;

        if(aBottom < bTop) 
            return false;
        if(bBottom < aTop) 
            return false;
        if(aRight < bLeft) 
            return false;
        if(bRight < aLeft) 
            return false;

        return true;
    }

    static int getRectSum(int si, int sj, int r, int c){
        // idxerror
        int ei = si + r -1;
        int ej = sj + c -1;
        return psum[ei][ej] - psum[si-1][ej] - psum[ei][sj-1] + psum[si-1][sj-1];
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        board = new int[N+1][M+1];
        psum = new int[N+1][M+1];

        for(int i =1; i<=N; i++){
            for(int j=1; j<=M; j++){
                board[i][j] = read();
            }
        }

        for(int i = 1; i<=N; i++){
            for(int j = 1; j<=M; j++){
                psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + board[i][j];
            }
        }

        int ans = -(1000 * 5 * 5) -1;
        for(int ai = 1; ai<=N; ai++){
            for(int aj = 1; aj<=M; aj++){
                for(int bi = 1; bi<=N; bi++){
                    for(int bj = 1; bj<=M; bj++){
                        if(ai == bi && aj == bj)
                            continue;

                        for(int ra = 1; ai + ra - 1 <= N; ra++){
                            for(int ca = 1; aj + ca - 1 <= M; ca++){

                                for(int rb = 1; bi + rb - 1 <= N; rb++){
                                    for(int cb = 1; bj + cb - 1 <= M; cb++){

                                        if(!isOverlap(
                                            ai, aj, ra, ca,
                                            bi, bj, rb, cb
                                        )){
                                            ans = Math.max(
                                                ans,
                                                getRectSum(ai, aj, ra, ca)
                                            + getRectSum(bi, bj, rb, cb)
                                            );
                                        }
                                    }
                                }

                            }
                        }

                    }//-->ai,aj,bi,bj(시작점잡기)
                }
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

기준점 두개 먼저 잡고 그걸 왼쪽 위로 하는 가능한 모든 직사각형에 대해 합 비교하기

누적합 전처리해가지고 직사각형 합 빨리 계산하기

psum[ei][ej] - psum[si-1][ej] - psum[ei][sj-1] + psum[si-1][sj-1];

r,c 를 두 직사각형에 대해 같게 해놓고 냈다가 계속 틀려서

r c r c 이렇게 for문이 총 8개나 겹치는 끔찍한 풀이가 되고 말았다..

---

문제 - 양수 직사각형의 최대 크기(모노토닉 스택)

https://www.codetree.ai/ko/trails/complete/curated-cards/test-max-area-of-positive-rectangle/description

양수 직사각형의 최대 크기 설명 | 코드트리

public class Main {
    static StreamTokenizer sst =
        new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException {
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N, M;
    static int[][] board;

    static int find(int[] height) {
        Deque<Integer> s = new ArrayDeque<>();
        int maxArea = 0;

        for (int i = 0; i <= M; i++) {
            int curHeight = (i == M ? 0 : height[i]);
            while (!s.isEmpty() && height[s.peekFirst()] > curHeight) {
                int h = height[s.pollFirst()];
                int w;
                if (s.isEmpty())
                    w = i;
                else 
                    w = i - s.peekFirst() - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            if (i < M)
                s.addFirst(i);
        }
        return maxArea;
    }

    public static void main(String[] args) throws Exception {
        N = read();
        M = read();
        board = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                board[i][j] = read();
            }
        }

        int[] height = new int[M];
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] > 0) 
                    height[j]++;
                else
                    height[j] = 0;
            }
            ans = Math.max(ans, find(height));
        }
        System.out.println(ans == 0 ? -1 : ans);
    }
}

사고의 흐름

문제 조건 ( 직사각형 내부가 전부 양수 여부 ) 에 의해 실제 입력값은 다음과 같이 양수면 1, 아니면 0으로 치환할 수 있다.

각 행을 어떤 바닥이라고 생각하면 위 입력은 1로 이루어진 히스토그램의 모양으로 볼 수 있다.
따라서 각 행마다 height라는 M크기의 배열을 정의하면, 이는 현재 행을 바닥이라 했을 때 위로 연속된 1의 갯수이다.

 

풀이

현재 행을 바닥으로 하는 최대 직사각형은 현재 height 배열의 히스토그램 최대 직사각형이 된다.

해당 문제는 각 막대를 직사각형의 최소 높이라고 생각해보면, 각 막대마다 자신보다 낮은 막대를
왼쪽과 오른쪽에서 처음 만나는 위치를 구하면, 해당 막대가 최소 높이인 최대 직사각형의 넓이를 계산할 수 있다.

 

구현

구현시, 단조 증가 스택에는 막대의 인덱스를 저장한다.

-> 높이 자체만 저장하면 너비를 계산할 수 없기 때문

현재 막대보다 낮은 높이를 만났을 때, 스택에서 막대를 꺼내면, 스택의 다음 원소가 왼쪽에서 처음 만나는 더 낮은 막대가 되고,
현재 위치가 오른쪽에서 처음 만나는 더 낮은 막대가 된다.

static int find(int[] height) {
    Deque<Integer> s = new ArrayDeque<>();
    int maxArea = 0;

    for (int i = 0; i <= M; i++) {
        int curHeight = (i == M ? 0 : height[i]);
        while (!s.isEmpty() && height[s.peekFirst()] > curHeight) {
            int h = height[s.pollFirst()];
            int w;
            if (s.isEmpty())
                w = i;
            else 
                w = i - s.peekFirst() - 1;
            maxArea = Math.max(maxArea, h * w);
        }
        if (i < M)
            s.addFirst(i);
    }
    return maxArea;
}

 

총 시간복잡도 = 각 행마다 최대 직사각형을 O(M) * N개의 행에 대해 수행 = O(NM)

입력을 한 줄씩 읽으면서 하면 공간 복잡도 O(M)도 가능할 듯.

 

토론에 누가 시간복잡도가 이게 맞나 이런 글이 있어서 이번 회고는 토론글에 팁으로 올려두었다. 

누군가한테는 도움이 되면 좋겠다. 

---

문제 - 컨베이어 벨트(배열 값 이동)

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-conveyor-belt/description

컨베이어 벨트 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,T;
    static int[] A;
    static int[] copy;


    public static void main(String[] args) throws IOException{
        N = read();
        T = read();

        A = new int[2*N];
        copy = new int[2*N];
        for(int i = 0; i<2*N; i++){
            A[i] = read();
        }

        for(int i = 0; i<2*N; i++){
            copy[(i+T)%(2*N)] = A[i]; 
        }

        StringBuilder sb = new StringBuilder();
        for(int  i = 0; i<copy.length; i++){
            sb.append(copy[i]);
            if(i == copy.length/2-1)
                sb.append("\n");
            else
                sb.append(" ");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

T초만큼 N 크기의 배열 2개가 있을때 값을 순환시키는 문제이다.

만약 이게 어떤 구현 문제의 부분문제가 된다면 어떤게 제일 효율적일지 고민했다. 

1) Deque로 구현하면 스왑이 O(1)이고 직관적이지만 객체 사용이 큰 오버헤드를 야기한다.

2) 배열로 하나하나 시뮬레이션하기 이것도 좀 별로고 원본이 손실되는 문제가 있다.

3) 입력배열, copy배열 나눠놓고 copy배열에 T를 offset으로 계산해서 최종 위치에 A[i] (원래 값)을 넣는 방식으로 업데이트하기

-> 3번이 제일 나아보이긴 한다. 근데 copy배열 쓰는게 공간 낭비일거 같기도 하다.

 

3번으로 구현해서 풀었다. 나머지 연산 사용해서 최종 인덱스에 원래 값을 넣는 방식으로 구현함.

---

문제 - 1차원 바람(구현) (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-The-1D-wind-blows/description

1차원 바람 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static char rc() throws IOException{
        sst.nextToken();
        return (char) sst.sval.charAt(0);
    }

    static int N,M, Q;
    static int[][] board;

    static boolean hasSameVal(int a, int b){
        for(int j = 0; j<M; j++){
            if(board[a][j] == board[b][j])
                return true;
        }
        return false;
    }

    static void shift(int a, int dir){
        int[] copy = new int[M];
        // 왼 -> 오
        if(dir == 1){ 
            for(int j=0;j<M;j++)
                copy[(j+1)%M] = board[a][j];
        }
        // 오 -> 왼
        else{ 
            for(int j=0;j<M;j++)
                copy[(j-1+M)%M] = board[a][j];
        }
        board[a] = copy;
    }

    //in-place 버전 copy 안쓰는거
    static void shift2(int a, int dir){
        // 왼->오
        if(dir == 1){
            int temp = board[a][M-1];
            for(int j=M-2;j>=0;j--)
                board[a][j+1] = board[a][j];
            board[a][0] = temp;
        }
        // 오->왼
        else{
            int temp = board[a][0];
            for(int j=1;j<M;j++)
                board[a][j-1] = board[a][j];
            board[a][M-1] = temp;
        }
    }

    static void wind(int srow, int sdir){
        shift2(srow, sdir);

        int updir = sdir;
        int downdir = sdir;
        int uprow = srow;
        int downrow = srow;

        // 위쪽 전파하고 아래쪽 전파 한번씩 하고 다시 
        while((uprow>=1) && hasSameVal(uprow, uprow-1)){
            updir = 1 - updir;
            shift2(uprow-1, updir);
            uprow--;
        }

        while((downrow < N-1) && hasSameVal(downrow, downrow+1)){
            downdir = 1- downdir;
            shift2(downrow+1, downdir);
            downrow++;
        }
    }

    static StringBuilder sb = new StringBuilder();
    static void boardPrint(){
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                sb.append(board[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }


    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        Q = read();
        board = new int[N][M];
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                board[i][j] = read();
            }
        }

        while(Q-->0){
            int row = read()-1;
            char type = rc();
            // dir = 1이 왼->오, 0이 오->왼
            int dir = 0;
            if(type == 'L')
                dir = 1;
            
            wind(row, dir);
        }
        boardPrint();
    }
}

사고의 흐름 및 풀이

1) 바람이 불 때 왼->오 방향 (L방향), 오->왼 방향 (R방향) 에 따라 배열이 회전 하는 것을 구현

2) 바람이 불때 shift 한 뒤, 그 결과물의 위쪽방향 열과 비교해서 하나라도 같으면 위쪽방향 열을 현재와 반대 방향으로 shift

-> 비교결과가 참일때 해당 방향(위 열, 아래 열)으로 계속 shifting 진행함

-> 끝 행에 도달하면 멈춰야 함.

 

디버깅할 게 많았는데, 방향 설정이 계속 헷갈렸고 

inplace 방식으로 배열 회전을 시도하다가 안돼서 copy 방식으로 해서 AC 받았는데

inplace 방식이 공간복잡도가 더 낮아서 템플릿으로 아래처럼 정리해둔다.

왼->오 면 맨 오른쪽 temp, [M-2, 0] -> board[j+1] = board[j] 해주고 board[0] = temp;
오->왼 이면 맨 왼쪽 temp, [1, M-1] -> board[j-1] = board[j] 해주고 board[M-1] = temp;

---

문제 - 십자 모양 폭발(배열 당기기) (다시 보기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-cross-shape-bomb/description

십자 모양 폭발 설명 | 코드트리

public class Main {
    static StreamTokenizer sst =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException {
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N;
    static int[][] board;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};

    // 1) 일단 0으로 터진부분 비움
    static void bomb(int si, int sj) {
        int range = board[si][sj];
        board[si][sj] = 0;
        for (int d = 0; d < 4; d++) {
            for (int k = 1; k < range; k++) {
                int ni = si + di[d] * k;
                int nj = sj + dj[d] * k;
                if (ni < 0 || ni >= N || nj < 0 || nj >= N)
                    break;
                board[ni][nj] = 0;
            }
        }
    }

    static void gravity() {
        for (int j = 0; j < N; j++) {
            int[] temp = new int[N];
            int idx = N - 1;

            for (int i = N - 1; i >= 0; i--) {
                if (board[i][j] != 0)
                    temp[idx--] = board[i][j];
            }

            for (int i = 0; i < N; i++) 
                board[i][j] = temp[i];
        }
    }

    public static void main(String[] args) throws Exception {
        N = read();
        board = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j] = read();
            }
        }
        int r = read() - 1;
        int c = read() - 1;
        bomb(r, c);
        gravity();
        print();
    }
}

사고의 흐름 및 풀이

처음에는 왼쪽, 오른쪽, 위+아래로 해서 열마다 폭발을 시키고 땡겨오는걸 구현하려했는데 이게 조건 계산이 너무 꼬여서

1) 일단 중심점에서 조건에 맞게 board에서 0으로 바꿔줌.

2) 그리고 모든 열에서 중간에 0 이 아닌 값만 [N-1, 0] 으로 아래에서부터 위로 보면서 

temp에 기록하고 board에 temp를 알맞게 붙여줌.

문제 조건상 bomb를 하면 빈 공간은 0이 되므로 temp의 크기는 처리하려는 열의 세로 길이와 같게 잡음.

static void gravity() {
    for (int j = 0; j < N; j++) {
        int[] temp = new int[N];
        int idx = N - 1;
        for (int i = N - 1; i >= 0; i--) {
        //이부분
            if (board[i][j] != 0)
                temp[idx--] = board[i][j];
        }
        for (int i = 0; i < N; i++) 
            board[i][j] = temp[i];
    }
}

---

문제 - 1차원 폭발 게임 (구현은 시킨대로 하기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-The-1D-bomb-game/description

1차원 폭발 게임 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N,M;
    static int[] A;

    // 폭발시킬 구간 s,e 반환
    static ArrayList<int[]> find(){
        ArrayList<int[]> li = new ArrayList<>();

        int i = 0;
        while(A[i] == 0){
            if(i == N-1){
                return li;
            }
            i++;
        }

        int s = i;
        int e = i;
        int curType = A[i++];
        int curCnt = 1;

        for(; i<N; i++){
            if(curType == A[i]){
                curCnt++;
                e = i;
            }
            else{
                if(A[i] == 0)
                    continue;
                if(curCnt >= M)
                    li.add(new int[]{s,e});
                
                curType = A[i];
                curCnt = 1;
                s = i;
                e = i;
            }
        }

        if(curCnt >= M)
            li.add(new int[]{s,e});
        return li;
    }

    static void bomb(List<int[]> li){
        for(int[] l : li){
            int s = l[0];
            int e = l[1];
            for(int i = s; i<=e; i++){
                A[i] = 0;
            }
        }
    }

    static void print(){
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        for(int i = 0; i<N; i++){
            if(A[i] != 0){
                cnt++;
                sb.append(A[i]).append("\n");
            }
        }
        String ss = sb.toString();
        System.out.print(cnt+"\n"+ss);
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        A = new int[N];
        for(int i= 0; i<N; i++)
            A[i] = read();
        
        while(true){
            ArrayList<int[]> li = find();
            //System.out.println(rst[0] +" "+rst[1]);
            if(li.isEmpty())
                break;
            bomb(li);
        }
        print();
    }
}

사고의 흐름

연속된 M개 이상의 클러스터가 존재하면 터뜨리고 여러개가 존재한다면 반드시 한꺼번에 터뜨려야 하는 문제다.

처음에 사실 터뜨릴곳 구간 구하고 터뜨리고 다음꺼 구간 구하고 터뜨리고 반복하면 같은 결과가 나올줄 알았는데

이게 예제에서는 돌아가서 되는줄 알았는데 제출해보니까 WA라 맞왜틀 30분했다. 

-> 제발 구현에서는 문제에서 시키는대로 하자.

 

풀이 및 반례

15 2
2 1 2 1 1 2 1 2 1 1 2 1 2 1 2
---------
2 1 2 0 0 2 1 2 1 1 2 1 2 1 2
2 1 0 0 0 0 1 2 1 1 2 1 2 1 2
2 0 0 0 0 0 0 2 1 1 2 1 2 1 2
0 0 0 0 0 0 0 0 1 1 2 1 2 1 2
0 0 0 0 0 0 0 0 0 0 2 1 2 1 2
-> 2 1 2 1 2 오답(내 풀이)
-------------
2 1 2 0 0 2 1 2 0 0 2 1 2 1 2
2 1 0 0 0 0 1 0 0 0 0 1 2 1 2
2 0 0 0 0 0 0 0 0 0 0 0 2 1 2
0 0 0 0 0 0 0 0 0 0 0 0 0 1 2
-> 2 1 2 정답

 

해당 처리 레벨에서 터뜨리는걸 동시에 하지 않으면

나중에 결과가 이상하게 영향을 미쳐서 지워져야할 클러스터가 제대로 지워지지 않는다. 

-> find의 반환 결과를 List로 변경하고 int[2] 에 start와 end를 담아주고 

List의 size가 0이면 더이상 터뜨릴 클러스트가 없으므로 반복문을 탈출한 후 

여기서는 값을 재사용하지 않으니 0을 스킵하고 출력한다.

---

문제 - 2차원 폭발 게임 (다시풀기)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-The-2D-bomb-game/description

2차원 폭발 게임 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N, M, K;
    static int[][] board;

    static boolean isAllZero(int[] A){
        for(int i = 0; i<N; i++){
            if(A[i] != 0)
                return false;
        }
        return true;
    }

    static void step1(){
        for(int j = 0; j<N; j++){
            int[] A = new int[N];
            for(int i = 0; i<N; i++){
                A[i] = board[N-1-i][j];
            }

            if(isAllZero(A))
                continue;
 
            while(true){
                // TODO: findpos li가 비어서나옴 -> 해결함
                ArrayList<int[]> li = findPos(A);
                if(li.isEmpty()){
                    // System.out.println("li is empty");
                    break;
                }
                bomb(A,li);
                A = pull(A);
                
            }

            for(int i = 0; i<N; i++){
                board[N-1-i][j] = A[i];
            }
            //pb();
        }
    }

    static ArrayList<int[]> findPos(int[] A){
        ArrayList<int[]> rst = new ArrayList<>();
        int i = 0;
        while((i < N) && A[i] == 0)
            i++;
        // 하..............
        if(i >= N)
            return rst;

        int prev = A[i];
        int s = i++;
        int cnt = 1;

        for(; i<A.length; i++){
            // prev는 0이 아니어야함!!!!!
            if(prev != 0 && prev == A[i]){
                cnt++;
            }
            else{
                if(cnt >= M){
                    int e = s + cnt - 1;
                    rst.add(new int[]{s, e});
                }
                s = i;
                prev = A[i];
                cnt = 1;
            }
        }
        //여기도
        if(prev != 0 && cnt >= M){
            rst.add(new int[]{s, s + cnt - 1});
        }
        return rst;
    }

    static int[] bomb(int[] A, ArrayList<int[]> li){
        for(int[] l : li){
            int s= l[0];
            int e = l[1];
            for(int i = s; i<=e; i++){
                A[i] = 0;
            }
        }
        return A;
    }

    static int[] pull(int[] A){
        int[] temp = new int[A.length];
        int zeros = 0;
        for(int i= 0; i<N; i++){
            if(A[i] != 0)
                temp[i-zeros] = A[i];
            else
                zeros++;
        }
        return temp;
    }

    static void step2(){
        int[][] copy = new int[N][N];

        for(int i = N-1; i>=0; i--){
            int[] A = new int[N];
            for(int j = 0; j<N; j++){
                A[j] = board[i][N-j-1];
            }

            if(isAllZero(A))
                continue;

            // A는 행을 오른쪽 -> 왼쪽으로 읽은 배열이라 당기면 오른쪽으로 당겨짐
            int[] t = pull(A);
            copy = rotate(t, i, copy);
        }
        board = copy;
    }

    // ci는 A 만들 당시 행번호임
    // A[i]를 차례대로 copy[N-1-i][N-1-ci]에 저장 
    static int[][] rotate(int[] t, int ci, int[][] copy){
        for(int i = 0; i<N; i++){
            copy[N-1-i][N-1-ci] = t[i];
        }
        return copy;
    }

    static int count(){
        int cnt = 0;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                if(board[i][j] > 0)
                    cnt++;
            }
        }
        return cnt;
    }

    // 디버그용 board, array print
    static void pb(){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                sb.append(board[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    static void pa(int[] A){
        StringBuilder sb = new StringBuilder();
        for(int j = 0; j<A.length; j++){
            sb.append(A[j]).append(",");
        }
        System.out.println(sb);
    }

    static int[] T = {1,1,1,2,2,3,5,2,2};

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        K = read();

        board = new int[N][N];
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                board[i][j] = read();
            }
        }

        while(K-->0){
            step1();
            step2();
        }
        step1();
        System.out.print(count());
    }
}

사고의 흐름 

먼저 문제를 읽으며 구현사항을 정리한다. 디버깅이 쉽게 함수화 시키고 시간이 남으면 최적화 고려했음.

 

step1
1) 모든 열에 대해서 세로로 A를 만듬
2) A에 대해서 M개 이상인 터뜨려야하는 구간들 list<int[2]> 반환함 (findPos)
3) empty list 가 나올때까지 계속 터뜨려 줌 (bomb)
4) 모든 열에 대해서 bomb가 끝났으면 모든 열에 대해서 세로 중력처리 해줌 (pullDown)
-> i = [0,N-1]일때, 
A[i]!=0 이면 temp[i-zerocount] = A[i], 
A[i]==0 zerocount++, 

step2
5) rotate에서는 빈 copyboard 하나 만들고 거기다가 돌린 최종값 업뎃 (rotate)
6) 모든 행에 대해서[N-1,0] (돌렸을때 맨밑이 1번째라서) 오른쪽 끝을 시작으로 하는 A를 만듬
7) 그리고 4번 방법 참고해서 temp에 오른쪽으로 민 배열 만들고
8) copyboard의 각 열[0,N-1] 의 아래쪽부터 세로로 temp [0,N-1] 값 저장
9) board = copy

주의
1~8) K번째까지 다하고 findpos+bomb+pulldown 해주고 출력
-> K*(step1 + step2) + step1

 

최적화 필요한 부분

List를 만들지 말고 바로 터뜨리기??

 

풀이 및 디버깅 

1) findPos

M개 이상 같은 부분이 있으면 A 배열에서 동시에 모두 찾아서 터뜨려줘야 하기 때문에 list로 모든 구간의 start와 end를 저장했다.

여기서 맨 처음 값을 찾을 때 prev 값은 반드시 0이 아니어야 하고 for문으로 순회를 다 하고 나서도 반드시 현재 cnt가 M개 이상인지 추가로 체크하고 list에 넣어서 반환해야 한다. 

 

2) pull

1. 원본 배열 board를 중력의 기준점을 0번 인덱스로 하는 값을 추출한 배열 A를 만든다.

2. bomb를 한 곳은 0이므로 새롭게 값을 덮어쓸 빈 배열 temp를 만든다.

3. 중간에 건너 뛸 0의 갯수를 세는 zeros를 선언하고

A[ i ] != 0 이면 temp[ i - zeros ] = A [ i ] ;

== 0 이면, zeros++

4. 1번과 반대로 집어넣으면 되는데 temp의 값을 집어넣어야 한다.

 

3) rotate

다 하고나서 board = copy 꼭 해줘야 한다

---

문제 - 떨어지는 1자 블록(상태 압축)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-falling-horizontal-block/description

떨어지는 1자 블록 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    // K는 1-based로 들어옴
    static int N,M,K;
    static int[][] board;
    static int[] H;

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        K = read()-1;
        
        board = new int[N][N];
        // H[j] = j열에 블록이 떨어졌을때 위치할 최대 위치
        // H N-1로 꼭 초기화해야함
        H = new int[N];
        Arrays.fill(H, N-1);

        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                board[i][j] = read();
            }
        }    

        for(int j = 0; j<N; j++){
            for(int i = 0; i<N; i++){
                if(board[i][j] != 0){
                    H[j] = i-1;
                    break;
                }
            }
        }

        int min = N-1;
        for(int j = K; j<=K+M-1; j++){
            min = Math.min(min, H[j]);
        }

        for(int j = K; j<=K+M-1; j++){
            H[j] = min;
            board[min][j] = 1;
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                sb.append(board[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

사고의 흐름

테트리스처럼 위에서 아래 방향으로 블록이 떨어지는 문제인데 1번만 떨어진다. 블록도 ㅡ 자 하나이다.

ㅡ 자 하나가 위치하는 최소값에 대한 추적을 하면 될거 같았다.

풀이

전체 보드에 대해서 열 단위로 블록이 떨어지면 놓일 자리를 값으로 갖는 H배열을 정의한다. 

그러면 떨어질 위치 K가 주어지게 되면 구간 [K, K+M-1] 에 대해 H배열의 최솟값을 구하고 그걸로 H배열을 업데이트한다.

-> 사실 1번만 하는거라 업데이트는 필요없다...

그리고 최솟값이 블록이 위치할 i가 되므로 board [ min ] [ K ] 부터 오른쪽으로 M칸 1로 채우고 print 하면 된다.

만약 1개가 아니라 10만개가 떨어진다면 구간값 구하는 H의 정의 그대로 가져가고 lazy 세그 써야할 것 같다.

---

문제 - 주사위 던지기(주사위 굴리기류 문제)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-roll-a-dice/description

주사위 던지기 설명 | 코드트리

import java.util.*;
import java.io.*;

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }
    static char rc() throws IOException{
        sst.nextToken();
        return sst.sval.charAt(0);
    }

    static int N,M,ci,cj;
    static int[][] board;

    // 6면 상태 저장하는 배열 만들고 
    // 0  ,  1,     2,     3,      4,     5
    // top, bottom, left, right, front, back?
    static int[] rotate(int[] d, int dir){
        if(dir == 0){
            int t = d[1];
            d[1] = d[2];
            d[2] = d[0];
            d[0] = d[3];
            d[3] = t;
        }
        else if(dir == 1){
            int t = d[1];
            d[1] = d[3];
            d[3] = d[0];
            d[0] = d[2];
            d[2] = t;
        }
        else if(dir == 2){
            int t = d[1];
            d[1] = d[5];
            d[5] = d[0];
            d[0] = d[4];
            d[4] = t;
        }
        else{
            int t = d[1];
            d[1] = d[4];
            d[4] = d[0];
            d[0] = d[5];
            d[5] = t;
        }
        return d;
    }
    //왼오위밑
    static int[] di = {0,0,-1,1};
    static int[] dj = {-1,1,0,0};

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        ci = read()-1;
        cj = read()-1;
        int[] dice = new int[]{1,6,4,3,2,5};

        board= new int[N][N];
        board[ci][cj] = dice[1];
        Map<Character, Integer> m = new HashMap<>();
        m.put('L', 0);
        m.put('R', 1);
        m.put('U', 2);
        m.put('D', 3);
        
        while(M-->0){
            char cmd = rc();
            int cd = m.get(cmd);
            int ni = ci + di[cd];
            int nj = cj + dj[cd];
            if(ni < 0 || nj < 0 || ni >= N || nj >= N)
                continue;
            dice = rotate(dice, cd);
            board[ni][nj] = dice[1];
            ci = ni;
            cj = nj;
        }

        int ans = 0;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                ans += board[i][j];
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름

처음에는 단순하게 6개의 면에서 왼오위밑 순서로 방문하면 무슨 면이 나올지 하드코딩했는데 

이게 주사위가 굴러가게 되면 처음 위치 기준에서 배열로 하드코딩한데로 따라가지가 않았다. 

-> 바닥면만 추적했다가 WA 받음

 

풀이

바닥면만 추적하는게 아니라 dice 전체 6면을 추적하게끔 배열로 두고

왼오위밑 방향 각각으로 굴렸을 때

그 방향에 놓인 4개의 면을 회전시키고 그걸 전부 업데이트하는 방식으로 구현해야 한다. 

 

예를 들어 왼쪽으로 굴린다면 왼-오에 관련된 4개의 면이 왼쪽 방향으로 회전하고, 

처음 temp는 bottom에 있는걸 잡고 prevFace = nextFace 로 갱신하면서 4개의 면을 전부 갱신한다. 

회전된 dice를 현재 dice에 갱신시키고 validation을 거친 ni,nj에 bottom에 해당하는 값을 덮어씌운 뒤,

ci=ni, cj=nj로 현재 좌표값을 갱신하고 M만큼 반복하면 완성

---

문제 - 대폭발(level BFS)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-big-explosion/description

대폭발 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    // 북동남서
    static int[] di = {-1,0,1,0};
    static int[] dj = {0,1,0,-1};
    static int N,M,si,sj;
    static int[][] board;

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        si = read()-1;
        sj = read()-1;
        board = new int[N][N];

        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{si,sj});
        board[si][sj] = 1;

        for(int ct = 1; ct<=M; ct++){
            int size = q.size();
            for(int n = 0; n<size; n++){
                int[] cur = q.poll();
                int ci = cur[0];
                int cj = cur[1];
                
                int nl = 1<<(ct-1);
                for(int d = 0; d<4; d++){
                    int ni = ci + nl*di[d];
                    int nj = cj + nl*dj[d];
                    if(ni < 0 || nj < 0 || ni >= N || nj >= N || board[ni][nj] == 1)
                        continue;
                    board[ni][nj] = 1;
                    q.add(new int[]{ni,nj});
                }
                // 원시 폭탄이 유지되고 t의 변화에 따라 새로운 위치에 폭탄 생성
                q.add(cur);
            }
        }

        int ans = 0;
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                ans += board[i][j];
            }
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

일단 BFS로 queue에 넣어서 한다는건 처음에 알았는데 이게 시간 관리가 있어서 queue에 상태로 추가할까 했는데 

그렇게 하면 같은 시간대에서 batch로 처리해야할 걸 처리하지 못하고 첫번째 ct가 M+1일때 탈출해버려서 오답이다. 

-> level BFS로 관리하는데 폭탄 위치 정하는 거에서 1<<(t-1)이라서 t=1로 시작한다.

 

level BFS이니까 배치 단위로 처리할 땐 반드시 q.size를 시간대마다 변수로 뽑아서 고정시켜놔야한다.

-> 안해두면 당연히 안에서 늘어나니까 레벨이 엉키게 된다. 

 

그리고 문제에서 원시 폭탄이 유지된다는게 그냥 거기 가만히 안터지고 있다는 뜻인줄 알았는데 

얘가 유지되면서 다음 t에서 새로운 거리로 새 폭탄들을 생성하는데 관여한다는 뜻이었다. 

따라서 4방향 적절히 validation 거친 새로운 위치들 + 기존위치까지 queue에 넣어주어야 한다.

---

문제 - 뱀 (deque + 조건 순서 중요)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-snake-loves-apples/description

뱀은 사과를 좋아해 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }
    static char rc() throws IOException{
        sst.nextToken();
        return (char) sst.sval.charAt(0);
    }

    //udrl
    static int[] di = {-1,1,0,0};
    static int[] dj = {0,0,1,-1};
    static int N,M,K;
    static int[][] board;

    public static void main(String[] args) throws IOException{
        N = read();
        board = new int[N][N];
        M = read();
        K = read();
        while(M-->0){
            int i = read()-1;
            int j = read()-1;
            board[i][j] = 1;
        }

        Map<Character, Integer> m = new HashMap<>();
        m.put('U', 0);
        m.put('D', 1);
        m.put('R', 2);
        m.put('L', 3);

        Deque<int[]> ss = new ArrayDeque<>();
        boolean[][] v = new boolean[N][N];
        v[0][0] = true;
        int time = 0;
        ss.addFirst(new int[]{0,0});

        outer:
        while(K-->0){
            char c = rc();
            int dir = m.get(c);
            int p = read();

            // ni,nj가 항상 1칸 앞이므로 peekFirst
            int[] cur = ss.peekFirst();
            int ci = cur[0];
            int cj = cur[1];
            
            for(int n = 1; n<=p; n++){
                int ni = ci + n*di[dir];
                int nj = cj + n*dj[dir];
                // 움직임 시도하면 무조건 time += 1
                time++;
                if(ni < 0 || nj < 0 || ni >= N || nj >= N)
                    break outer;

                ss.addFirst(new int[]{ni,nj});
                if(board[ni][nj] == 1)
                    board[ni][nj] = 0;
                else{
                    int[] last = ss.pollLast();
                    v[last[0]][last[1]] = false;
                }

                if(v[ni][nj])
                    break outer;
                v[ni][nj] = true;
            }
        }
        System.out.print(time);
    }
}

사고의 흐름

잘 알려진 뱀 문제이다. 사과를 먹으면 꼬리가 없어지지 않고 사과를 안먹는다면 꼬리가 없어져야 한다.

명령수는 K이며 다음 칸으로 넘어가는 시도를 할 때마다 time 이 1씩 증가되어야만 한다.

Deque는 삽입/삭제가 O(1)이며, pos I, J를 저장해서 뱀을 나타내고 머리를 참조할 때는 peekFirst로 해야 한다.

-> 이 문제 조건상 항상 머리보다 앞에 다음 칸이 위치하며 pollFirst로 해버리면 머리가 삭제되어버린다.

 

여기서 while 문에다가 alias를 달아서 내부 반복문이든 if문이든 바로 아래 있는 조건문이 아니더라도 

문제의 3가지 종료 조건 (invalid ni,nj, v[ni][nj] = true, K 명령수 처리는 while문 자체에서 필터링하므로 해당 없음)을 만족하면 바로 탈출할 수 있게 break outer로 빠져나온다. 

-> 자바에서 반복문 alias는 for, while, do-while에 모두 적용할 수 있음

핵심 풀이

1) peekFirst로 머리 i,j 가져옴

2) p만큼 머리 앞쪽의 다음 ni,nj 구함 -> 움직임을 시도했으니 time++

3) ni,nj validation 진행함 -> 종료 분기 

4) ni,nj를 뱀의 머리로 추가하고

만약 ni,nj가 1이였다면 0으로 보드 업뎃하고

아니라면 꼬리칸은 deque에서 제거한 뒤, 점유 표시를 false로 풀어준다.

5) ni, ni를 visited에서 true인지 보기 -> 종료 분기

-> 반드시 ni,nj visited를 꼬리 제거 이후에 해줘야 함

6) K만큼 반복

---

문제 - 숫자의 순차적 이동(8방향 inplace 보드 업데이트)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-sequential-movement-of-numbers/description

숫자의 순차적 이동 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int N, M;
    static int[][] board;
    static Map<Integer, int[]> toMove;
    static int[] di = {-1,-1,0,1,1,1,0,-1};
    static int[] dj = {0,1,1,1,0,-1,-1,-1};

    static void move(){
        for(int k : toMove.keySet()){
            int ci = toMove.get(k)[0];
            int cj = toMove.get(k)[1];

            int max = 0;
            int mi = -1;
            int mj = -1;
            for(int d = 0; d<8; d++){
                int ni = ci + di[d];
                int nj = cj + dj[d];
                if(ni < 0 || nj < 0 || ni >= N || nj >= N)
                    continue;
                if(board[ni][nj] > max){
                    max = board[ni][nj];
                    mi = ni;
                    mj = nj;
                }
            }

            int t = board[ci][cj];
            board[ci][cj] = board[mi][mj];
            board[mi][mj] = t;

            // 원인 : 한번 스왑할때마다 바로 tomove에서 위치 스왑해줘야함.
            toMove.put(max, new int[]{ci,cj});
            toMove.put(t, new int[]{mi,mj});
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        board = new int[N][N];
        // [n][i,j]= 숫자 n의 좌표 위치 i,j 저장
        toMove = new HashMap<>();

        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                int cn = read();
                board[i][j] = cn;
                toMove.put(cn, new int[]{i,j});
            }
        }

        for(int t = 0; t<M; t++){
            move();
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                sb.append(board[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

사고의 흐름 및 풀이

N*N 크기의 보드에 [1, N*N] 의 숫자가 1개씩만 등장할 때, 1부터 N*N까지 순서대로 인접한 8방향의 숫자들중 가장 큰 값과 스왑하는 연산을 M번 했을 때 보드의 상태를 출력하는 문제이다.

매번 N*N 보드를 순회하면서 이번 숫자를 찾는거보단 HashMap을 이용해서 <숫자, [ i, j ]> 로 한번에 찾아주게 했다. 

 

HashMap은 key 값의 정렬이 보장이 안되지만 이 문제에서 되는 이유는 

정확히 숫자가 1개씩 등장하기 때문에 집합이 유지되기 때문이다. 

-> 키가 위치가 아닌 값이기 때문에

 

그리고 8방향에 대해 max 값과 mi,mj 값을 찾고 바로 board에서 inplace swap을 해 준다. 

또한 HashMap에 바로 찾아야할 값의 위치를 업데이트 시켜 준다.

-> 이렇게 하지 않고 마지막에 하나 다 돌고 하게 되면 값만 바뀌고 위치가 안 바뀌어서 엉뚱한 결과로 이어진다. 

---

문제 - 합쳐지는 구슬들

https://www.codetree.ai/ko/trails/complete/curated-cards/test-merge-marbles/description

합쳐지는 구슬들 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }
    static char rc() throws IOException{
        sst.nextToken();
        return (char) sst.sval.charAt(0);
    }
    
    static int N,M,T;
    static int[] ctoi = new int[128];
    // 번호, i,j,dir,weight
    static Map<Integer, int[]> ball = new HashMap<>();
    //북동남서
    static int[] di = {-1,0,1,0};
    static int[] dj = {0,1,0,-1};

    //1초 이동
    static void move(){
        // <cn, cd, cw> [i][j]
        ArrayList<int[]>[][] board = new ArrayList[N][N];
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                board[i][j] = new ArrayList<>();
            }
        }

        for(int cn : ball.keySet()){
            int[] cur = ball.get(cn);
            int ci = cur[0];
            int cj = cur[1];
            int cd = cur[2];
            int cw = cur[3];

            int ni = ci + di[cd];
            int nj = cj + dj[cd];
            int nd = cd;

            // 반대로 방향만 뒤집기
            if(ni < 0 || nj < 0 || ni >= N || nj >= N){
                ni = ci;
                nj = cj;
                nd = (cd+2)%4;
            }
            
            board[ni][nj].add(new int[]{cn, nd, cw});
        }

        ball = new HashMap<>();
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                if(board[i][j].isEmpty())
                    continue;
                int mn = 0;
                int md = -1;
                int wSum = 0;

                for(int[] it : board[i][j]){
                    int cn = it[0];
                    int cd = it[1];
                    int cw = it[2];

                    if(cn > mn){
                        mn = cn;
                        md = cd;
                    }
                    wSum += cw;
                }

                ball.put(mn, new int[]{i,j,md,wSum});
            }
        }
    }

    public static void main(String[] args) throws IOException{
        ctoi['U'] = 0;
        ctoi['R'] = 1;
        ctoi['D'] = 2;
        ctoi['L'] = 3;

        N = read();
        M = read();
        T = read();
        for(int m=1; m<=M; m++){
            ball.put(m, new int[]{read()-1,read()-1,ctoi[rc()],read()});
        }

        for(int t = 0; t<T; t++){
            move();
        }

        int cnt = ball.size();
        int max = 0;
        for(int cn : ball.keySet()){
            int[] b = ball.get(cn);
            max = Math.max(max, b[3]);
        }
        System.out.print(cnt+" "+max);
    }
}

사고의 흐름

2차원 격자에 구슬이 주어지고 구슬마다 번호, i 좌표, j 좌표, 진행 방향, 무게 가 주어졌을 때

T초가 지난 뒤 구슬의 갯수와 가장 무거운 구슬 무게를 출력하는 문제이다.
벽에 부딪히게 되면 방향을 바꾸고 방향을 바꾸는데 1초가 걸린다 했으니 move에서는 방향 만 바꾼다.

 

ctoi는 배열로 구현했는데 char가 int로 내부에서 처리되므로 map대신 128 크기의 배열로 받아서 바로 처리한다.

-> 아스키 코드로 처리하므로 128 은 고정

 

풀이

move는 3단계로 나눌 수 있다.

1) 모든 구슬이 동시에 움직이므로 깊은 복사가 필요하고 격자당 구슬에 (번호, 방향, 무게) 가 필요하므로 

ArrayList 2차원 배열로 선언한 뒤 list 초기화 진행

 

2) 구슬의 정보가 들어있는 Map ball에 대해서 각 구슬을 이동시키고 board에 저장함. 

-> 겹치는건 list.add되므로 각 격자에 쌓여있다고 생각하면 됨.

 

3) ball에 new HashMap으로 재할당 후, 모든 보드를 보면서 list가 empty가 아닌 격자에서 겹쳐 있다면 조건대로 실행.

사실 1개만 있어도 maxNum 초기값이 0이고 wSum이 0에서 시작하므로 따로 구분 안하고 똑같이 처리하면 된다.

-> 가장 큰 구슬 번호를 찾았을때 그 방향도 저장하고 wSum은 누적해준다.

해당 격자 내의 모든 구슬을 처리해줬을 때, ball.put(mn, new int[] { i, j, md, wSum }) 으로 구슬 리스트 재작성

 

T만큼 위 단계를 반복하고 ball을 Iterator로 접근하던지 keySet()을 쓰던지 해서 순회하면서 정답 갱신 후 출력

---

문제 - 쌓인 숫자의 순차적 이동(자료구조 활용)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-sequential-movement-of-stacked-numbers/description

쌓인 숫자의 순차적 이동 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static int[][] mBoard;
    static Deque<Integer>[][] board;
    static int N,M;
    // 숫자, i,j 좌표값 추적 (1~N*N 전부 추적)
    static int[][] m2;
    static int[] di = {-1,-1,0,1,1,1,0,-1};
    static int[] dj = {0,1,1,1,0,-1,-1,-1};

    static void move(int cur){
        int ci = m2[cur][0];
        int cj = m2[cur][1];

        //8방향중 제일 큰 값 존재하는 ni,nj를 mi,mj로 선정
        int max = 0;
        int mi = -1;
        int mj = -1;
        for(int d = 0; d<8; d++){
            int ni = ci + di[d];
            int nj = cj + dj[d];
            if(ni < 0 || nj < 0 || ni >= N || nj >= N)
                continue;
            if(mBoard[ni][nj] > max){
                max = mBoard[ni][nj];
                mi = ni;
                mj = nj;
            }
        }

        // 만약 선택된 숫자의 인접 8방향에 숫자없으면 움직이지 않음
        if(mi == -1)
            return;

        //cur가 존재하는 칸에서 
        // cur 위에있는거 전부 다 빼서 옮겨야 하는 칸으로 옮기고
        // 이때 대표값이 바뀐다면 mBoard[ni][nj] 값도 바꿔줌
        // 1) mi,mj로 옮길 cur포함한 cur위 숫자들 모음
        Deque<Integer> li = new ArrayDeque<>();
        while(true){
            int top = board[ci][cj].pollLast();
            if(top == cur){
                li.addFirst(top);
                break;
            }
            li.addFirst(top);
        }

        // cur+cur위 제거된 ci,cj의 mBoard 대표값 갱신
        Iterator it = board[ci][cj].iterator();
        int nmax = 0;
        while(it.hasNext()){
            nmax = Math.max(nmax, (int) it.next());
        }
        mBoard[ci][cj] = nmax;

        // cur+cur위 숫자들 mi,mj로 옮기고
        // mBoard mi,mj 대표값 갱신
        // m(숫자, i,j) 갱신
        while(!li.isEmpty()){
            int next = li.pollFirst();
            if(next > mBoard[mi][mj]){
                mBoard[mi][mj] = next;
            }
            board[mi][mj].addLast(next);
            m2[next] = new int[]{mi,mj};
        }
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        mBoard = new int[N][N];
        board = new Deque[N][N];
        m2 = new int[N*N+1][2];
        for(int i= 0; i<N; i++){
            for(int j = 0; j<N; j++){
                board[i][j] = new ArrayDeque<>();
            }
        }

        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                int n = read();
                mBoard[i][j] = n;
                board[i][j].addLast(n);
                m2[n] = new int[]{i,j};
            }
        }

        while(M-->0){
            int cur = read();
            move(cur);
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                if(board[i][j].isEmpty())
                    sb.append("None");
                else{
                    while(!board[i][j].isEmpty())
                        sb.append(board[i][j].pollLast()).append(" "); 
                }
                sb.append("\n");
            }
        }
        System.out.print(sb);
    }
}

사고의 흐름

숫자가 여러개가 동시에 존재할 수 있는 2차원 배열이 존재하고 M개의 이동해야하는 숫자가 주어질 때, 문제 조건에 따라 이동한 뒤 보드의 상태를 출력하는 문제다. 출력할때는 위에 있는 것부터 출력한다.

처음에 생긴걸 보고 스택을 생각했는데 삽입할때 아래에서부터 삽입하고 그래야해서 Deque 2차원 배열로 구성했다. 

 

2차원 Deque board, 각 i,j 좌표의 max value를 추적하는 mBoard, 각 숫자의 좌표를 추적하는 map 을 뒀다. 

mBoard는 8방향 탐색시 그때마다 board를 쌓인 숫자만큼 탐색하는건 말도 안된다고 생각해서 O(1)로 하기 위해 뒀는데 사실상 나중에 mBoard의 ci, cj를 갱신할때 크기만큼 재탐색하기 때문에 시간 복잡도가 엄청 줄어들진 않은 것 같다. 

map은 board에서 어떤 숫자가 거기 있는지 없는지 확인하는것도 좀 그래서 추적용으로 추가했다. 

-> 사실 HashMap은 공간복잡도를 과하게 늘리는 면이 있어서 int[ N*N+1 ][ 2 ] 로 개선했다.

-> m2[ next ] = new int[]{ mi, mj };

 

풀이

먼저 2차원 보드를 입력받을 때 deque board와 mBoard를 초기화하고 map도 초기화한다.

그리고 M개의 움직일 숫자를 받아 move를 진행한다.

 

1) 8방향에서 0보다 큰 max값을 찾는다.

-> 만약 mi,mj 값을 찾지 못해 -1이 남아있다면 move 하지 않는다.

 

2) 움직일 임시 deque를 구성한다.

-> pollLast 한 값이 cur일때까지 뽑아서 구성

 

3) board ci, cj에서 떠나갈 값들이 뽑혔으므로 mBoard ci,cj 값을 갱신한다.

 

4) board mi,mj 에 임시 deque를 pollFirst한 값을 addLast로 붙여주고 

여기서 새로 들어온 값이 mBoard mi,mj보다 클 수 있으므로 mBoard 값도 최대로 갱신한다.

또한 map 값도 위치가 바뀌었으므로 put으로 덮어쓰기한다.

 

시간 복잡도 계산

8방향 탐색 O(1) + 숫자 분리 O(H) + 출발 칸 최댓값 재계산 O(H) + 목적지 이동 O(H)

최악의 경우 모든 숫자가 한칸에 모일 수 있으므로 H = N*N

따라서 O(MN^2)

---

문제 - 구슬의 이동

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-marble-movement/description

구슬의 이동 설명 | 코드트리

public class Main {
    static StreamTokenizer sst = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }
    static char rc() throws IOException{
        sst.nextToken();
        return (char) sst.sval.charAt(0);
    }

    static int N,M,T,K;
    // 북동남서
    static int[] ctoi = new int[128];
    static int[] di = {-1,0,1,0};
    static int[] dj = {0,1,0,-1};
    static HashMap<Integer, int[]> ball = new HashMap<>();

    static void move(){
        HashMap<Integer, int[]> cBall = new HashMap<>();
        // [0]=번호,[1]=속도
        // !! 보드는 격자 계산용임. 업데이트해야하는건 ball map
        PriorityQueue<int[]>[][] copy = new PriorityQueue[N][N];
        for(int i= 0; i<N; i++){
            for(int j = 0; j<N; j++){
                copy[i][j] = new PriorityQueue<>((a,b)->{
                    if(a[1] != b[1])
                        return a[1] - b[1];
                    return a[0] - b[0];
                });
            }
        }

        for(int cn : ball.keySet()){
            int[] cur = ball.get(cn);
            int ci = cur[0];
            int cj = cur[1];
            int cd = cur[2];
            int cv = cur[3];

            // 주기성 이용해서 최적화해야함
            for(int v = 0; v<cv % (2*(N-1)); v++){
                int ni = ci + di[cd];
                int nj = cj + dj[cd];
                if(ni < 0 || nj < 0 || ni >= N || nj >= N){
                    // 방향 바꾸는데 시간 안 듬
                    cd = (cd + 2)%4;
                    ni = ci + di[cd];
                    nj = cj + dj[cd];
                }
                ci = ni;
                cj = nj;
            }

            // ci, cj에 음수값
            // ball 업데이트안해서->cBall추가로 사용
            copy[ci][cj].add(new int[]{cn, cv, cd});
        }

        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                // 이렇게 하려면 우선순위 문제랑 반대로 구현해야함
                while(copy[i][j].size() > K){
                    copy[i][j].poll();
                }
                for(int[] cc : copy[i][j]){
                    int ccn = cc[0];
                    int ccv = cc[1];
                    int ccd = cc[2];
                    cBall.put(ccn, new int[]{i,j,ccd,ccv});
                }
            }
        }

        ball = cBall;
    }

    public static void main(String[] args) throws IOException{
        N = read();
        M = read();
        T = read();
        K = read();

        ctoi['U'] = 0;
        ctoi['R'] = 1;
        ctoi['D'] = 2;
        ctoi['L'] = 3;

        for(int m = 1; m<=M; m++){
            int r = read()-1;
            int c = read()-1;
            int d = ctoi[rc()];
            int v = read();
            ball.put(m, new int[]{r,c,d,v});
        }

        for(int t = 0; t<T; t++){
            move();
        }
        System.out.print(ball.size());
    }
}

 

---

#구현 #시뮬레이션 #코드트리 #코딩테스트 #코테공부