2018 KAKAO BLIND RECRUITMENT 프렌즈4블록 파이썬

2018 KAKAO BLIND RECRUITMENT 프렌즈4블록 파이썬 풀이

이번 문제는 레벨 2입니다.

접근방식

1. 각각의 블록에서 4칸을 탐색하는 함수가 필요하다.
2. 문제는 바로 지우는 게 아니고 기억해뒀다가 탐색이 끝나면 한번에 지워야 한다.
3. 지우고 난 후 블록이 빈 공간을 채우도록 바꿔주고 다시 탐색을 진행한다.
4. 종료되는 시점은 아무것도 지워지지 않을 때 answer를 return 해준다.

문제 풀이를 고민하면서 어려웠던 점은, 지워진 자리에 블록을 아래부터 채우는 과정과
더 이상 지워지는 블록이 없다는 것을 판별하기 위해서 어떤 조건을 통해 비교해야 하는지 어려웠습니다.

• 결국 제 코드로 문제를 풀지는 못했지만, 블록을 찾아 지우고 def 함수를 좀 더 익힐 수 있었습니다.
• 모범 답안은 구글링을 통해 tjdud0123님의 velog 를 참고했습니다.

내 풀이(오답)

def match(i, j):
    return((i,j), (i, j+1), (i+1, j), (i+1, j+1))

def move(board, i, j, m):
    maxv = i
    for s in range(m):
        if board[s][j] == "0":
            maxv = max(i, s)
    return i, maxv
    # while True:
    #     i += 1
    #     if board[i+1][j] != '0':
    #         break
    # return i, j

def solution(m, n, board):
    answer = 0
    index_list = []
    board = [list(i) for i in board]
    visited = [[False]* n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i < m-1 and j < n-1:
                b1, b2, b3, b4 = match(i, j)
                # print(b1, b2, b3, b4)
                if (board[b1[0]][b1[1]] == board[b2[0]][b2[1]] == board[b3[0]][b3[1]] == board[b4[0]][b4[1]]) and(visited[b1[0]][b1[1]] == visited[b2[0]][b2[1]] == visited[b3[0]][b3[1]] == visited[b4[0]][b4[1]]== False):
                    index_list.append(b1)
                    index_list.append(b2)
                    index_list.append(b3)
                    index_list.append(b4)
    index_list = set(index_list)
    answer += len(index_list)
    for x, y in index_list:
        board[x][y] = '0'
        visited[x][y] = True


    for a in range(m-1):
        for b in range(n):
            if (board[a+1][b] == '0') and (visited[a][b] == False) and (board[a][b] != '0'):
                # print('a',a, 'b',b)
                c, d = move(board, a, b, m)
                board[c][d] = board[a][b]
                visited[c][d] = False
                board[a][b] = '0'
                visited[a][b] = True
    new_board = board.copy()
    return m, n, answer, board, visited

제 코드에서 문제점은, 입출력 예시 1에 대해서는 블록 찾기와 채워지는 것이 올바르지만,

입출력 예시 2부터는 블록 찾는 함수 또한 오작동했습니다.

이 코드에서 해결해야 할 문제점은 인접한 4개의 블록을 정확하게 찾고, 채워진 board를 다시 입력값으로 가져가서

함수를 반복하는 방법입니다.

모범코드

def pop_num(b, m, n):
    pop_set = set()
    # search
    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)])
    # set_board
    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

’	=’ 연산자를 통해 update를 할 수 있다는 것을 처음 알게 되었습니다. 이후 count 함수를 이용해서 지워진 블록의 갯수를 찾아줍니다.

while문 안에 pop_num을 넣어주어서, pop == 0 일 때, 즉 하나도 지워지지 않는다면 count를 리턴해줍니다.

이번 문제에서는 def 함수를 적절히 생성하고, 반복해서 실행해주는 것이 중요했던 시뮬레이션 문제였습니다.

구현과 시뮬레이션 문제에 특히 어려움을 많이 느끼는데 연습이 많이 필요한 것 같습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.

Just do it & Keep steady