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

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] [1차] 프렌즈 4블록

새로 알게된 것들

카카오 문제를 보면 카카오는 구현하는 문제를 좋아하는게 느껴진다. 이번 문제도 마찬가지이다. 카카오 비문학 국어 문제를 독해하면서 4블록이 없어지는 부분에서 겹치는 부분, 중복되는 부분만 잘 해결하면 문제가 풀리겠다는 생각이 들었다. 그래서 바로 코드를 짜기 시작했다. 이제 알고리즘문제를 단순히 실력을 늘리기 위해 풀기 보단 빠르게 코딩테스트를 통과해야 겠다는 생각으로 문제를 풀면서 변수 이름이나 어떻게 더 짧게 리팩토링을 할까라는 생각을 절제하면서 어떻게든 한번에 통과해야겠다는 생각으로 문제를 풀었다.

풀이

1. 주어진 보드가 문자열이 1차원 리스트로 저장되어 있어 이것을 2차원 리스트로 변환하는 작업을 하였다. 문자열은 값을 변경하기 힘들기 때문에 꼭 필요한 작업인 것 같다.

2. 사라지는 블럭들 중에 중복되는 블록은 기존의 블럭에서 사라질 때마다 answer에 +1을 해주어 처리했다. 기존의 블럭이 아닌 사라진 블럭에서 사라진 블럭으로 바뀌는 것이기 때문에 중복을 처리할 수 있다.

3. 사라진 블럭보다 위에 있는 살아있는 블럭들을 아래로 내릴 때 모든 인덱스를 돌면서 현재 블럭이 사라진 블럭이면 위의 블럭과 스위칭을 해준다. 이렇게 스위칭 해준 블럭이 가장 위에 있는 블럭일 때까지 해주어 블럭이 떨어지는 것을 구현했다. 문제의 다른 부분들은 쉽게 구현했는데 여기서 좀 막혔다. 반복문의 i와 j이 지역변수인 줄 알고 계속 인덱스를 돌때마다 초기화되어 바로 값을 초기화해주어도 상관없는 줄 알았지만 뒤에 인덱싱을 할때도 영향을 미쳤다. 그래서 x, y = i, j을 해주어 해결했다.

4. 무한 반복문을 돌면서 만약 4블럭이 없을 경우 탈출하도록 했다.

5. 마스크를 만들어 모든 마스크가 만족하면 4블록으로 리스트에 저장하여 1번에서 사라지는 블럭들로 이용하였다.

코드

def solution(m, n, board):
    mask = [(0, 1), (1, 0), (1, 1)]
    non_block = '@'
    new_board = list(map(lambda x: list(x), board)) # 문자열을 2차원리스트로 변환
    delete = [] # 사라지는 블록들
    answer = 0
    while True:
        for x, y in delete:
            if new_board[x][y] != non_block:
                new_board[x][y] = non_block
                answer += 1

        delete = []
        for i in range(m):
            for j in range(n):
                x, y = i, j # x, y로 변환하지 않고 그냥 i, j로 쓰면 안됨. i, j가 그냥 지역변수가 아닌듯
                if new_board[x][y] == non_block:
                    while (x, y) != (0, y):
                        new_board[x][y], new_board[x - 1][y] = new_board[x - 1][y], new_board[x][y]
                        x = x - 1

        is_delete = False # 4블록이 있는지 확인 있으면 True
        for i in range(m - 1):
            for j in range(n - 1):
                block = new_board[i][j]
                if block == non_block: continue
                temp_delete = [(i, j),]
                flag = True
                for x, y in mask:
                    if block != new_board[i + x][j + y]:
                        flag = False
                        break
                    temp_delete.append((i + x, j + y),)
                if flag:
                    is_delete = True
                    delete += temp_delete

        if not is_delete:
            break

    return answer

1. 마을과 거리에 대한 리스트를 사용하기 쉬운 형태로 변환
2. 각 마을의 방문여부 리스트만 만들고 각 마을의 거리에 대한 정보를 담는 리스트는 만들지 않음
3. 시작점 마을 1을 우선순위 큐에 넣고 반복문 시작
4. 이미 방문한 마을인 경우 스킵
5. 다익스트라 알고리즘 특성상 이전보다 더 작은 거리인 마을이 pop 될 수 없기 때문에 pop한 마을의 거리가 K보다 클 경우 반복문을 빠져나오고 카운팅한 방문을 반환
6. 4,5번에 해당되지 않을 경우 현재 마을에서 갈 수 있는 마을들을 우선순위큐에 누적거리와 함께 push
7. 위의 과정 반복

느낀점

저번 학기 알고리즘 수업을 듣고 다익스트라 알고리즘이 익숙해 조금 수월하게 풀었다. 다른 사람들도 우선순위큐를 이용해서 가장 작은 거리를 구했을 거라고 예상하며 다른사람 풀이는 보는데 내 코드와 많이 달라 놀랐다. 문제를 푸는 동안 어떻게 하면 더 시간을 줄일 수 있을까라는 생각을 했는데 일단 문제는 풀고 그런 생각을 해야겠다. 그리고 구조적으로 크게 시간을 줄이지 못하면 코드를 더 간결하고 더 단순하게 짜는 연습이 필요해 보인다.