[파이썬] [1차] 프렌즈4블록

문제 설명

프렌즈4블록

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT 
RRFACC 
RRRFCC 
TRRRAA 
TTMMMF 
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력 형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예제

m	n	board	answer
4	5	["CCBDE", "AAADE", "AAABF", "CCBBF"]	14
6	6	["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"]	15

예제에 대한 설명

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

해설 보러가기

카카오 신입 공채 1차 코딩 테스트 문제 해설

 

 

✨ 나의 풀이

def solution(m, n, board) :
    answer=0
    board=list(map(list, zip(*board)))

    def pop() :
        pop_set=set()
        for x in range(1, n) :
            for y in range(1, m) :
                if board[x][y] == board[x-1][y] == board[x-1][y-1] == board[x][y-1] != 0 :
                    pop_set |= {(x, y), (x-1, y), (x-1, y-1), (x, y-1)}
        return pop_set

    def move() :
        nonlocal answer
        for i in pop_set :
            answer+=1
            x, y= i[0], i[1]
            board[x][y]=0
        for i in range(n) :
            board[i]=board[i].count(0)*[0] + [board[i][j] for j in range(m) if board[i][j] != 0]

    while True :
        pop_set=pop()
        if pop_set :
            move() # 함수 호출
        else :
            break

    return answer

1. 2차원 리스트 board를 zip을 이용해 전치행렬(행과 열이 바뀐 행렬) 생성

2. pop 메소드를 호출해서 set을 받는다. set이 비었으면 while문을 break

3. pop 메소드에서 2*2 크기의 터질 블록을 찾는다. 행과 열은 1부터 시작해서 범위를 넘지 않도록 한다.

4. move 메소드에서 터질 블록이 담긴 set에서 좌표를 꺼내고, 해당 위치의 값을 0으로 한다.

board의 행에 0과(터진 블록들) 남은 블록들을 생성해 넣는다.

 

 

# 풀다가 중단
from collections import deque

def bfs(x, y, board, block):
    que = deque([(x, y)])
    len_x = len(board)
    len_y = len(board[0])
    visited = [[0] * len_y for i in range(len_x)]
    visited[x][y]=1
    cnt=1

    while que:
        r, c = que.popleft()
        for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0):
            nx, ny = r + dx, c + dy
            if 0 <= nx < len_x and 0 <= ny < len_y :
                if not visited[nx][ny] and board[nx][ny] == block :  # 같은 블럭
                    que.append((nx, ny))
                    visited[nx][ny] = 1
                    cnt+=1
    print(cnt)
    return visited


def solution(m, n, board):
    answer = 0
    for i in range(m) :
        for j in range(n) :
            visited=bfs(i, j, board, board[i][j])
    return answer

bfs로 풀려다가 어떻게 2*2 정사각형인 것을 알지?

visited를 또 for문으로 순회하면서 세야하나.... 생각이 들어 풀다가 중단

 

 

// 미완성
import java.util.*;

class Main {
    public static void main(String[] args) {
        int answer = 0;
        int m=6;
        int n=6;
        String[] board={"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"};

        // 전치행렬
        String[][] board1=new String[m][n];
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                board1[i][j]=board[j].substring(i, i+1);
                board1[j][i]=board[i].substring(j, j+1);
            }
        }

        ArrayList board2=new ArrayList<>(Arrays.asList(board1));

    }

    public static void playing(ArrayList<ArrayList<String>> board, int x, int y){
        HashSet<> set=new HashSet();
        for(int i=1; i < board.size(); i++){
            for(int j=1; j < board.get(0).size(); j++){
                if(board.get(i).get(j).equals(board.get(i).get(j-1).equals(board.get(i-1).get(j-1).equals(board.get(i-1).get(j)))) && !board.get(i).get(j).equals("_")){

                }
            }
        }

    }
}

풀다가 점점 이상해지는 것 같아서 ㅠ.ㅠ....

 

 

📌 다른 사람 풀이

 

# https://velog.io/@tjdud0123/%ED%94%84%EB%A0%8C%EC%A6%88-4%EB%B8%94%EB%A1%9D-2018-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EA%B3%B5%EC%B1%84-python
def pop_num(b, m, n) :
    pop_set=set()
    
    for i in range(1, n) :
        for j in range(1, m) :
            if b[i][j] == b[i-1][j-1] == b[i-1][j] == b[i][j-1] != '_':
                pop_set |= set([(i, j), (i-1, j-1), (i-1, j), (i, j-1)])
    
    # 블록 터뜨리기
    for i, j in pop_set :
        b[i][j]=0
    for i, row in enumerate(b) :
        empty=['_']*row.count(0)
        b[i]=empty+[block for block in row if block != 0]
    return len(pop_set)


def solution(m, n, board) :
    count=0
    b=list(map(list, zip(*board)))
    
    while True :
        pop=pop_num(b, m, n)
        if pop == 0 : return count
        count+=pop

T	R	R	T	T	T
T	R	R	R	T	M
T	F	R	R	M	M
A	A	F	R	M	T
N	C	C	A	M	T
T	C	C	A	F	J

위와 같이 board(테케 2번 예시) 행과 열을 바꾼다. 블럭이 떨어지는 것을 표현하기 편하다.

zip은 iterable의 i번째를 모아 i번째 튜플에 담아 반환한다.

튜플은 값 변경이 불가해서 map을 사용해서 각 행의 타입을 리스트로 변환한다.

우측 아래를 기준으로 정사각형 2*2 범위 내에서 순회한다.

i와 j가 1부터 시작하는 것은 우측 아래 기준점이 될 수 없어서다.

2*2 범위 내의 블록의 문자가 모두 같고 "_"이 아니면 pop_set에 합집합을 한다.

pop_set에 들어있는 원소는 터뜨릴 블록이다.

터뜨릴 블록의 값은 0으로 처리한다.

한 행의 0의 갯수만큼 _를 넣고 0이 아닌 값과 이어붙여서 행을 수정한다.

pop_num 함수의 반환값이 0이 될때까지 블록 터뜨리기가 반복된다.

 

 

# https://velog.io/@wisepine/Programmers-%ED%94%84%EB%A0%8C%EC%A6%884%EB%B8%94%EB%A1%9D-python
def solution(m, n, board) :
    board=list(map(list, zip(*board)))       # 전치행렬
    
    def game(b) :
        pops=0
        sc=[i[:] for i in b]
        for i in range(1, n) :
            for j in range(1, m) :
                if b[i][j] == -1 : continue
                if b[i][j] == b[i-1][j] == b[i-1][j-1] == b[i][j-1] :
                    sc[i][j], sc[i-1][j], sc[i-1][j-1], sc[i][j-1]=0, 0, 0, 0
                    
        for i, v in enumerate(sc) :
            cnt=v.count(0)
            pops+=cnt
            sc[i]=[-1]*cnt+[a for a in v if a != 0] #-1은 빈공간
        
        return sc, pops
    
    answer=0
    while True :
        board, pops=game(board)
        if pops == 0 : return answer
        answer+=pops

위와 같은 알고리즘

 

 

// https://velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%94%84%EB%A0%8C%EC%A6%884%EB%B8%94%EB%A1%9D-Java
class Solution{
    public int solution(int m, int n, String[] board){
        int answer=0;
        char[][] map=new char[m][n];

        for(int i=0; i<m; i++){
            map[i]=board[i].toCharArray();
        }

        while(true){
            int cnt=checkBlock(m, n, map);
            if(cnt == 0) break;
            answer+=cnt;

            dropBlock(m, n, map);
        }
        return answer;
    }
	
    //  블럭이 위에서 아래로 떨어짐
    private static void dropBlock(int m, int n, char[][] map){
        for(int c=0; c<n; c++){
            for(int r=m-1; r >= 0; r--){       
                if(map[r][c] == '.'){
                    for(int nr=r-1; nr >= 0; nr--){
                        if(map[nr][c] != '.'){
                            map[r][c]=map[nr][c];
                            map[nr][c]='.';
                            break;
                        }
                    }
                }
            }
        }
    }
	// 블럭이 있으면 checkFour를 호출해서 2*2가 되는지 확인
    private static int checkBlock(int m, int n, char[][] map){
        int cnt=0;
        boolean[][] isChecked=new boolean[m][n];

        for(int i=0; i<m-1; i++){
            for(int j=0; j<n-1; j++){
                if(map[i][j] == '.') continue;
                checkFour(map, isChecked, i, j);
            }
        }
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(isChecked[i][j]){
                    cnt++;
                    map[i][j]='.';
                }
            }
        }
        return cnt;
    }
	
    // 2*2 블럭 찾기
    private static void checkFour(char[][] map, boolean[][] isChecked, int i, int j){
        char block=map[i][j];

        for(int r=i; r<i+2; r++){
            for(int c=j; c<j+2; c++){
                if(map[r][c] != block) return;
            }
        }

        for(int r=i; r<i+2; r++){
            for(int c=j; c<j+2; c++){
                isChecked[r][c]=true;	// 터질 블럭
            }
        }
    }
}

자바로 구현하니 코드가 길다😅

전치행렬로 바꾸지 않고 구현

dropBlock 메소드의 구현 내용이 직관적으로 이해가 되지 않아 정리해본다.

r은 행이다. 아래에서 0까지 올라가면서 .이 있는 위치 map[r][c]를 찾는다.

.이 나온 후부터 0까지 올라가면서 블럭값 map[nr][c]를 찾는다.

찾은 블럭값 map[nr][c]를 .이 있는 위치에 넣으면 블럭이 떨어진 것으로 표현 할 수 있다.

 

 

 

문제 출처 👉 프로그래머스