[ Baekjoon - 10/13 ] - 20061번: 모노미노도미노2

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

20061번: 모노미노도미노 2

 

• 소요 시간 : 3시간..

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 512MB
   • 문제
     
     • 블록을 놓을 횟수(1≤N≤10,000), t개의 블럭 종류(1≤t≤3)
     • 좌표 x(0≤x≤3), y(0≤y≤3)

     • 

     • 빨간색 영역 안에서 3가지 종류의 블럭중 하나를 놓으면, 각각 초록색, 파란색 영역으로 떨어진다.
       
     • 빨간영역에 블럭을 놔둔 좌표를 기준으로 초록영역은 같은 열에 맞게 떨어지고, 파란영역은 같은행에 맞게 떨어진다.
     • 떨어질때 이미 밑에 블럭이 있다면 그 위로 떨어져야한다(초록 파랑 둘다)
     • 초록색 영역을 기준으로 같은 행일때, 파란색 영역을 기준으로 같은 열일때 블럭은 사라진다.
     • 블럭이 사라졌다면 위의 블럭을 내려와야한다.
   • 이해
     • 문제가 전체 케이스에 따른 조건을 준다기 보다도, 케이스에 의존적인 이동을 보여주기만해서 더 난해했던 문제였다.. 확실한 근거보다도 상상에 맡긴 이동을 하게되서(난 테트리스를 생각했다) 좋아하지 않는 문제서술이지만 2번과정을 통해 과정을 공통화 시키고자 했다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 문제에서 준 절차를 따라가보며 문제에서 하고자 하는 실행을 그려보았고, 이를 단계화 해보았다.
     1. 빨간영역에 (1x1), (1x2), (2x1)중 하나의 블록을 골라 원하는 좌표에 놔둔다.
     2. 빨간영역에 둔 블록은 초록색 바닥, 파란색 바닥을 향해 같이 떨어지게 되는데, 진행방향에 이미 블럭이 있다면 그 위에 쌓이게 된다.
     3. 2번을 N개의 횟수만큼 실행하면서
        초록영역의 같은 행에서의 모든 열, 파란영역의 같은 열에서의 모든 행에 블럭이 있다면 이는 삭제되고,
        초록영역은 위의 블럭, 파란영역은 좌측블럭을 내린다.
     4. 2번을 N개의 횟수만큼 실행하면서
        블럭이 초록/파란 영역의 연한색 부분에 위치하게 된다면, 
        빨간영역에서 해당 색 방향으로 연한색 부분에 침범한 만큼(최대 2) 밀어서 이동시킨다.
   • 이렇게 정리할 수 있었다... 걍 문제를 이렇게 줬으면 얼마나 좋아ㅠ
3. 문제를 어떻게 해결할 것인가
   • 위 문제는 2번에 정리한 단계대로 따라가면 되는 문제라 아이디어 자체는 어렵지 않았다.
4. 위 계획을 검증
   • 하라는 대로 하는거니까.. 
   • 굳이 있다면 시간복잡도 인데, 그거는 구현할때 구현체를 어떻게 잡느냐가 사실상 큰 변동사항이므로 최대한 작게 저장하는 식으로 구현하면된다. 
   • 많이 저장하면 그만큼 반복문도 많이 돌릴테고 결국 많은 연산을 하게되니까.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            public static int N,ans=0;
            public static int[][] blueMap = new int[4][6];
            public static int[][] greenMap = new int[6][4];
            public static int[][] blocks;
        
            public static void main(String[] args) throws IOException {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st;
        
                N = Integer.parseInt(br.readLine());
                blocks = new int[N][3];
        
                for(int i=0; i<N; i++) {
                    st = new StringTokenizer(br.readLine(), " ");
                    for(int j=0; j<3; j++) {
                        blocks[i][j] = Integer.parseInt(st.nextToken());
                    }
                }
        
                for(int[] block : blocks) {
                    int t = block[0];
                    int x = block[1];
                    int y = block[2];
        
                    green(t, x, y);
                    blue(t, x, y);
        
                    remove();
                    specialZone();
                }
                finish();
        
            }
            public static void green(int t, int x, int y) {
                for(int i=0; i<6; i++) {
                    if(t == 1) {
                        if(i == 5) greenMap[i][y] = 1;
                        else {
                            if(greenMap[i][y] == 0 && greenMap[i+1][y] == 1) {
                                greenMap[i][y] = 1;
                                break;
                            }
                        }
                    }else if(t == 2) {
                        if(i == 5) greenMap[i][y] = greenMap[i][y+1] = 1;
                        else {
                            if(greenMap[i][y] == 0 && greenMap[i][y+1] == 0) {
                                if(greenMap[i+1][y] == 1 || greenMap[i+1][y+1] == 1) {
                                    greenMap[i][y] = greenMap[i][y+1] = 1;
                                    break;
                                }
                            }
                        }
                    }else {
                        if(i == 4) {
                            greenMap[i][y] = greenMap[i+1][y] = 1;
                            break;
                        }else {
                            if(greenMap[i][y] == 0 && greenMap[i+1][y] == 0) {
                                if(greenMap[i+2][y] == 1) {
                                    greenMap[i][y] = greenMap[i+1][y] = 1;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        
            public static void blue(int t, int x, int y) {
                for(int i=0; i<6; i++) {
                    if(t == 1) {
                        if(i == 5) blueMap[x][i] = 1;
                        else {
                            if(blueMap[x][i] == 0 && blueMap[x][i+1] == 1) {
                                blueMap[x][i] = 1;
                                break;
                            }
                        }
                    }else if(t == 2) {
                        if(i == 4) {
                            blueMap[x][i] = blueMap[x][i+1] = 1;
                            break;
                        }else {
                            if(blueMap[x][i] == 0 && blueMap[x][i+1] == 0) {
                                if(blueMap[x][i+2] == 1) {
                                    blueMap[x][i] = blueMap[x][i+1] = 1;
                                    break;
                                }
                            }
                        }
                    }else {
                        if(i == 5) blueMap[x][i] = blueMap[x+1][i] = 1;
                        else {
                            if(blueMap[x][i] == 0 && blueMap[x+1][i] == 0) {
                                if(blueMap[x][i+1] == 1 || blueMap[x+1][i+1] == 1) {
                                    blueMap[x][i] = blueMap[x+1][i] = 1;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        
            public static void specialZone() {
                int cnt = 0;
        
                for(int i=0; i<=1; i++) {
                    for(int j=0; j<4; j++) {
                        if(greenMap[i][j] == 1) {
                            cnt++;
                            break;
                        }
                    }
                }
                while(cnt-- > 0) {
                    for(int i=0; i<4; i++) {
                        for(int j=5; j>0; j--) {
                            greenMap[j][i] = greenMap[j-1][i];
                        }
                        greenMap[0][i] = 0;
                    }
                }
        
                cnt = 0;
                for(int i=0; i<=1; i++) {
                    for(int j=0; j<4; j++) {
                        if(blueMap[j][i] == 1) {
                            cnt++;
                            break;
                        }
                    }
                }
                while(cnt-- > 0) {
                    for(int i=0; i<4; i++) {
                        for(int j=5; j>0; j--) {
                            blueMap[i][j] = blueMap[i][j-1];
                        }
                        blueMap[i][0] = 0;
                    }
                }
            }
        
            public static void remove() {
                int line = 0, gIdx = -1, bIdx = -1;
        
                for(int i=2; i<6; i++) {
                    int cnt = 0;
        
                    for(int j=0; j<4; j++) {
                        if(greenMap[i][j] == 1) cnt++;
                    }
                    if(cnt == 4) {
                        for(int j=0; j<4; j++) greenMap[i][j] = 0;
                        gIdx = i;
                        line++;
                    }
                }
        
                ans += line;
                while(line-- > 0) {
                    for(int i=0; i<4; i++) {
                        for(int j=gIdx; j>0; j--) {
                            if(greenMap[j][i] == 1) continue;
                            int temp = greenMap[j][i];
                            greenMap[j][i] = greenMap[j-1][i];
                            greenMap[j-1][i] = temp;
                        }
                    }
                }
        
                line = 0;
                for(int i=2; i<6; i++) {
                    int cnt = 0;
                    for(int j=0; j<4; j++) {
                        if(blueMap[j][i] == 1) cnt++;
                    }
                    if(cnt == 4) {
                        for(int j=0; j<4; j++) blueMap[j][i] = 0;
                        bIdx = i;
                        line++;
                    }
                }
        
                ans += line;
                while(line-- > 0) {
                    for(int i=0; i<4; i++) {
                        for(int j=bIdx; j>0; j--) {
                            if(blueMap[i][j] == 1) continue;
                            int temp = blueMap[i][j];
                            blueMap[i][j] = blueMap[i][j-1];
                            blueMap[i][j-1] = temp;
                        }
                    }
                }
            }
        
        
            public static void finish() {
                int cnt = 0;
                for(int i=0; i<6; i++) {
                    for(int j=0; j<4; j++) {
                        if(greenMap[i][j] == 1) cnt++;
                        if(blueMap[j][i] == 1) cnt++;
                    }
                }
        
                System.out.println(ans);
                System.out.println(cnt);
            }
        }

   2. Python 3

      • N = int(input())
        blue = [[0]*6 for _ in range(4)]
        green = [[0]*4 for _ in range(6)]
        point = 0
        
        def goBlue(t,xx,yy):
            global blue, green
            x = xx
            y = 0
            if t == 1:
                while True:
                    if y > 5 or blue[x][y] != 0:
                        y -= 1
                        blue[x][y] = 1
                        break
                    y += 1
            if t == 2:
                y = 1
                while True:
                    if y > 5 or blue[x][y] != 0 :
                        y -= 1
                        blue[x][y] = 1
                        blue[x][y-1] = 1
                        break
                    y += 1
            if t == 3:
                x1 = x
                x2 = x+1
                while True:
                    if y > 5 or blue[x1][y] != 0 or blue[x2][y] != 0:
                        y -= 1
                        blue[x1][y] = 1
                        blue[x2][y] = 1
                        break
                    y += 1
        
        def goGreen(t,xx,yy):
            global green
            x = 0
            y = yy
            if t == 1:
                while True:
                    if x > 5 or green[x][y] != 0:
                        x -= 1
                        green[x][y] = 1
                        break
                    x += 1
            elif t == 2:
                y1 = y
                y2 = y + 1
                while True:
                    if x > 5 or green[x][y1] != 0 or green[x][y2] != 0:
                        x -= 1
                        green[x][y1] = 1
                        green[x][y2] = 1
                        break
                    x += 1
            elif t == 3:
                x = 1
                while True:
                    if x > 5 or green[x][y] != 0:
                        x -= 1
                        green[x][y] = 1
                        green[x-1][y] = 1
                        break
                    x += 1
        
        def greenDel():
            global green
            idx = 0
            check = False
            for i in range(2):
                for j in range(4):
                    if green[i][j] == 1:
                        idx = i
                        check = True
                        break
                if check:
                    break
            if check == True:
                if idx == 0:
                    for i in range(3, -1, -1):
                        for j in range(4):
                            green[i+2][j] = green[i][j]
                            green[i][j] = 0
                    return 2
                elif idx == 1:
                    for i in range(4, -1, -1):
                        for j in range(4):
                            green[i+1][j] = green[i][j]
                            green[i][j] = 0
                    return 1
            return 0
        def blueDel():
            global blue
            idx = 0
            check = False
            for j in range(2):
                for i in range(4):
                    if blue[i][j] == 1:
                        idx = j
                        check = True
                        break
                if check:
                    break
            if check == True:
                if idx == 0:
                    for j in range(4):
                        for i in range(3, -1, -1):
                            blue[j][i+2] = blue[j][i]
                            blue[j][i] = 0
                    return 2
                elif idx == 1: 
                    for j in range(4):
                        for i in range(4, -1, -1):
                            blue[j][i+1] = blue[j][i]
                            blue[j][i] = 0
                    return 1
            return 0
        def checkGreen():
            global green
            idx = 5
            green_ans = 0
            while True:
                if idx < 2:
                    break
                linecnt = 0
                for j in range(4):
                    if green[idx][j] == 1:
                        linecnt += 1
                if linecnt == 4:
                    green_ans += 1
                    for i in range(idx-1, -1, -1):
                        for j in range(4):
                            green[i+1][j] = green[i][j]
                    continue
                else:
                    idx -= 1
        
            return green_ans
        
        def checkBlue():
            global blue
            idx = 5
            blue_ans = 0
            while True:
                if idx < 2:
                    break
                linecnt = 0
                for i in range(4):
                    if blue[i][idx] == 1:
                        linecnt += 1
                if linecnt == 4:
                    blue_ans += 1
                    for j in range(4):
                        for i in range(idx-1, -1, -1):
                            blue[j][i + 1] = blue[j][i]
                    continue
                else:
                    idx -= 1
            return blue_ans
        
        ans=0
        for i in range(N):
            t,x,y = map(int, input().split())
            goBlue(t,x,y)
            goGreen(t,x,y)
            ans += checkGreen()
            ans += checkBlue()
            blueDel()
            greenDel()
        
        print(ans)
        
        cnt = 0
        for i in range(4):
            for j in range(6):
                if blue[i][j] == 1:
                    cnt += 1
        
        for i in range(6):
            for j in range(4):
                if green[i][j] == 1:
                    cnt += 1
        print(cnt)

 

• 결과