프로그래머스)[1차] 프렌즈 4블록

https://school.programmers.co.kr/learn/courses/30/lessons/17679

프로그래머스

 

def solution(m, n, board):
    answer = 0
    
    arr = []
    
    for i in range(len(board)):
        a = list(board[i])
        arr.append(a)
        
    remove_idx = []

    def dfs(x,y,char):
        dx = [0,1,1]
        dy = [1,0,1]
        isTrue = True
        for i in range(3):
            nx = dx[i] +x
            ny = dy[i] + y
            
            if (0 <= nx < m) and (0 <= ny < n):
                if char != arr[nx][ny]:
                    isTrue = False
            else:
                isTrue = False
        if isTrue == True:
            if [x, y] not in remove_idx:
                remove_idx.append([x, y])
                
            if [x+0,y+1] not in remove_idx:
                remove_idx.append([x+0,y+1])
                
            if [x+1,y+0] not in remove_idx:
                remove_idx.append([x+1,y+0])
            
            if [x+1, y+1] not in remove_idx:
                remove_idx.append([x+1, y+1])
        
    
    while True :
        for i in range(len(arr)):
            for j in range(len(arr[0])):
                if arr[i][j] != '_':
                    dfs(i,j,arr[i][j])
                    
#         4개가 같은지 찾는거
        

        if len(remove_idx) == 0:
            break
#         remove_idx 길이가 0이면, 즉 리스트 안에 맞는게 하나도 없다면 break
        answer += len(remove_idx)
        for idx in remove_idx:
            arr[idx[0]][idx[1]] = '_'
        
            
#             4개 찾은걸 _로 바꿔줌

        # for i in range(len(arr)):
        #     for j in range(len(arr[0])):
        #         if i < len(arr) - 1 and arr[i+1][j] == '_':
        #             arr[i+1][j] = arr[i][j]
        #             arr[i][j] = '_'
        
        for i in range(len(arr)-1, -1,-1):
            for j in range(n):
                if arr[i][j] == '_' :
                    for k in range(i,-1,-1):
                        if arr[k][j] != '_':
                            arr[k][j],arr[i][j] = arr[i][j],arr[k][j]
                            break
        
#         자기 바로 아래에 _라면 아래로 내림
        remove_idx = []
#     remove_idx 초기화

        
    return answer

해당 문제는 조금 애를 먹은 듯하다.

우선 2차원 배열을 보면 자동으로 dfs,bfs를 떠올려 그것을 이용해 풀려고 했지만 거리가 2 이하, 그것도 2x2 를 확인해야하니 dfs bfs는 조금 낭비같았다.

그래서 생각해낸 방법이 arr[i][j]를 기준으로 우측,아래, 우측대각선아래 만 확인하는 방법이었다.

그 방법을 생각해낸 뒤론 순항이었다.

우측,아래,대각우측을 확인해 2x2면 해당 인덱스를 remove_idx 배열에 append.

그리고 리스트의 모든 확인이 끝나면 remove_idx의 길이만큼 answer를 ++

다음으론 remove_idx에 들어간 인덱스를 확인하며 해당 문자를 '_'로 바꿔주었다.

마지막으로 뻥 뚫린 블록( 코드에선 '_')에 채워넣는 일인데, 여기서 조금 많은 생각을 했다.

결국 m부터 0까지 확인해서 만일 arr[k][j]가 '_'라면 arr[k-1][j] arr[k-2][j].... 을 확인해서 하나라도 문자가 나온다면 위치를 바꿔주고 break.

break를 하는 이유는 치환이 중복되면 안되서이다.

예를들어 

[
1
2
_
_
]

가 있다고 치자.

그럼 아래로 내려간 결과

[
_
_
1
2
]

가 나와야 하지만

break를 해주지 않을 경우

[
_
_
2
1
]

로 완전히 다른 값이 된다.

 

위 공식을 계속 따르며 remove_idx 즉, 2x2배열이 없을 경우 while문을 빠져나온다.