[프로그래머스] 프렌즈4블록 파이썬

프렌즈4블록 ( https://programmers.co.kr/learn/courses/30/lessons/17679 )

처음에는 dfs나 bfs를 사용해야 하는 느낌이었지만 그렇지 않았습니다. 무조건 4개일 경우에만 블럭이 사라지는 방식이었기 때문에 다른 방법으로 코딩을 진행하게 되었습니다.

문제 해결

• 입력받은 문자열로 이루어진 board 배열을 다루기 쉽도록 하기 위해 각각의 문자로된 리스트 board로 변경해 주었습니다.
• 이제 이 board를 [0,0] 부터 마지막까지 탐색을 진행하면서 [0,0], [0,1], [1,0], [1,1] 과 같이 4개의 사각형 좌표가 모두 같은 문자인 곳을 탐색하여 해당 좌표들을 전역 리스트인 basket에 담아줍니다. => def check(x, y, board)
• 위의 탐색이 끝난 뒤 만약 basket이 비어있다면 더 이상 사라진 블록이 없는 것이므로 종료하면 되고, 비어있지 않다면 basket에 들어온 좌표들을 모두 "0"(비어있음 표시) 으로 변경해 준 뒤 위에 블록이 존재한다면 빈칸으로 내려줍니다. => def empty(m, n, board)
• 위의 과정을 반복하며 check를 해도 basket이 비어있다면 종료합니다.

basket = []; 		#4개의 블록이 사각형을 이뤄 지워져야할 블록의 좌표를 담아줄 리스트

#board를 모두 돌며 4개의 사각형을 이루는 블록이 있는지 체크합니다.
#발견하였고 이 사각형이 "0"(비어있음)으로 이루어져 있지 않다면 basket에 담아줍니다.
def check(x, y, board): 

    global basket;
    #입력받읕 x,y를 기준으로 오른쪽, 아래, 오른쪽 아래부분을 확인하여
    #네가지 값이 모두 같을 경우 4개의 사각형을 이룬다고 판단합니다.
    a = board[x][y];
    b = board[x][y+1];
    c = board[x+1][y];
    d = board[x+1][y+1];
    
    if a == b == c == d and a != "0":
    	#사각형을 이룬다고 판단하면 모든 좌표를 basket에 추가해줍니다.
        basket.append([x,y]);
        basket.append([x,y+1]);
        basket.append([x+1,y]);
        basket.append([x+1,y+1]);
    
    return;

#"0"(비어있음)표시가 완료된 board의 블록들의 빈칸을 채워주기 위해
#블록들을 내려줍니다.
def empty(m, n, board):
		
    for y in range(n):
    
    	#빈칸을 발견한다면 담아줄 리스트 입니다.
        point = [];
        
        #세로축은 빈값이 아래부터 찾아야 하기 때문에 아래부터
        #위 방향으로 탐색을 합니다.
        for x in range(m-1, -1, -1):
        	
            #아직 빈칸을 발견하지 못했을 때
            #새로운 빈칸을 발견한다면 해당 좌표를 point에 추가해줍니다.
            if not point:
                if board[x][y] == "0":
                    point.append([x,y]);
            
            #빈칸이 하나라도 존재할 경우에
            else:
            	#또 빈칸을 발견하면 이어서 point에 추가해줍니다.
                if board[x][y] == "0":
                    point.append([x,y]);
                    
                #빈칸을 발견한 상태에서 빈칸이 아닌 문자를 발견하였다면
                else:
                    a, b= point.pop(0); 	#가장 먼저 발견한 빈칸의 좌표를 a,b에 담아줍니다.
                    board[a][b] = board[x][y];	#문자를 a,b 좌표에 넣어준 다음
                    board[x][y] = "0";		#문자를 발견했던 x,y 좌표를 빈칸으로 만들어 줍니다.
                    point.append([x,y]);	#그리고 새로 빈칸이 된 x,y 좌표를 다시 point에 담아줍니다.
                    
    return board;

def solution(m, n, get_board):
    global basket;
    answer = 0;
    key = True;
    board = [];
    
    #board를 다루기 쉽게 하기 위해 list 형식으로 변경해 주었습니다.
    for g in get_board:
        board.append(list(g));
    
    while key:
        
        #어차피 탐색을 할 때 x+1, y+1같이 사각형임을 포함할 것이기 때문에
        #m-1, n-1 까지만 반복을 하였습니다.
        for x in range(m-1):
            for y in range(n-1):
            	#블록체크!
                check(x, y, board);
         
        #만약 basket의 값이 있다면 빈값을 처리해야합니다.
        if basket:
            #basket값을 하나씩 확인하며 "0"으로 변경해 준 뒤 지워진 블록의 개수를 추가해줍니다.
            for x, y in basket:
                if board[x][y] != "0":
                    board[x][y] = "0";
                    answer += 1;
            #빈값으로 처리를 해주었으니 basket은 비워두어 다음을 준비합니다.
            basket.clear();
        
        #basket이 비어있다면 while을 종료합니다.
        else:
            break;
        
        #board 빈값 채우기!
        board = empty(m, n, board);
    
    return answer;
	

=> 몇 가지 부분에서 어려움을 겪었지만 혼자 해결할 수 있었던 문제입니다. empty 함수에서 문자를 빈칸(a,b)으로 옮겨준 뒤 문자의 위치였던 (x,y)를 빈칸으로 표시를 해 주었으나 해당 (x,y)를 다시 point에 추가를 해줘야 했었는데 그 부분을 알지 못해 시간을 많이 보냈습니다. 다음에 또 풀어보면 좋을 문제인 것 같습니다.