[프로그래머스 Level2] 프렌즈4블록
📃 문제 설명
프렌즈4블록
👨💻 해결 방법
나의 생각의 흐름을 주절주절..
4개가 붙어있는 경우 블록을 터뜨려야하므로,
보드를 돌면서 4개가 붙어있는 경우를 체크하여 좌표를 저장한다.
이 때, 중복을 방지하기 위해 set을 사용했다.
그리고 set에 저장된 좌표를 빈자리로 만들고 다시 보드를 도는 방식으로 반복하다가, 더 이상 터뜨릴 블록이 없을 때(set이 비어있을 때)종료하면 된다.
그런데 생각해봐야할 문제가, 두 가지 있었다.
첫 번째로, 중간에 있는 블록이 터질경우 윗 블록들이 아래로 떨어져야 하는데, 이것을 처리해야 한다.
보드가 2차원 리스트로 주어지기 때문에 아래로 떨어지는 것을 구현하기가 복잡했다. 그래서 보드를 우측으로 90도 회전시켰다. 그렇게 되면 한 행을 큐의 개념으로 pop시키면 우측 블록들이 자연스럽게 빈공간을 채우게 된다.
하지만 여기서 두 번째 문제가 생긴다.
한 행에서 터뜨려야 할 블록이 두 개 이상일 때, 미리 저장되어 있는 좌표들에 pop을 사용하면 pop되면서 인덱스가 꼬인다.
나는 이 문제를 해결하기 위해, 우선 터뜨려야 할 자리를 바로 pop하지 않고 0으로 채웠다.
그리고 다시 그 행에서 0이 아닌 값들로만 채운 배열을 만들고 그 뒤에 0의 갯수만큼 -1을 채워서 행을 완성한다. 이렇게 하면 가운데 블록들이 사라지고 빈자리를 우측블록이 채우게 된다.
이 때 -1은 빈자리를 의미하므로 터뜨려야할 블록을 체크할 때 -1은 예외처리 해주었다.
결론
보드를 우측으로 90도 회전하여, 블록이 터지면 위에서 아래로 블록이 체워지는게 아니라 우측에서 좌측으로 채워지도록 하여, 큐의 개념을 활용하여 구현했다.
보드를 돌면서 4개가 붙어있는 경우 좌표를 저장하고, 더 이상 터뜨릴 블록이 없을 때 까지 반복하며, 블록을 터트리고 빈자리를 -1로 채우는 과정을 반복한다.
블록이 터질 때 마다 횟수를 카운트하여 반환하면 끝
👨💻 소스 코드
def solution(m, n, board):
answer = 0
newBoard = []
for i in range(n):
temp = []
for j in range(m - 1, -1, -1):
temp.append(board[j][i])
newBoard.append(temp)
while True:
boom = set()
for i in range(1, n):
for j in range(1, m):
if newBoard[i - 1][j - 1] == newBoard[i - 1][j] == newBoard[i][j - 1] == newBoard[i][j] != -1:
boom |= {(i, j), (i - 1, j - 1), (i - 1, j), (i, j - 1)}
if not boom:
break
for i, j in boom:
newBoard[i][j] = 0
for i in range(n):
newBoard[i] = [item for item in newBoard[i] if item != 0]
for k in range(m - len(newBoard[i])):
newBoard[i].append(-1)
answer += 1
return answer
Author And Source
이 문제에 관하여([프로그래머스 Level2] 프렌즈4블록), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@choiyunh/프로그래머스-Level2-프렌즈4블록
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
프렌즈4블록
나의 생각의 흐름을 주절주절..
4개가 붙어있는 경우 블록을 터뜨려야하므로,
보드를 돌면서 4개가 붙어있는 경우를 체크하여 좌표를 저장한다.
이 때, 중복을 방지하기 위해 set을 사용했다.그리고 set에 저장된 좌표를 빈자리로 만들고 다시 보드를 도는 방식으로 반복하다가, 더 이상 터뜨릴 블록이 없을 때(set이 비어있을 때)종료하면 된다.
그런데 생각해봐야할 문제가, 두 가지 있었다.
첫 번째로, 중간에 있는 블록이 터질경우 윗 블록들이 아래로 떨어져야 하는데, 이것을 처리해야 한다.
보드가 2차원 리스트로 주어지기 때문에 아래로 떨어지는 것을 구현하기가 복잡했다. 그래서 보드를 우측으로 90도 회전시켰다. 그렇게 되면 한 행을 큐의 개념으로 pop시키면 우측 블록들이 자연스럽게 빈공간을 채우게 된다.
하지만 여기서 두 번째 문제가 생긴다.
한 행에서 터뜨려야 할 블록이 두 개 이상일 때, 미리 저장되어 있는 좌표들에 pop을 사용하면 pop되면서 인덱스가 꼬인다.나는 이 문제를 해결하기 위해, 우선 터뜨려야 할 자리를 바로 pop하지 않고 0으로 채웠다.
그리고 다시 그 행에서 0이 아닌 값들로만 채운 배열을 만들고 그 뒤에 0의 갯수만큼 -1을 채워서 행을 완성한다. 이렇게 하면 가운데 블록들이 사라지고 빈자리를 우측블록이 채우게 된다.
이 때 -1은 빈자리를 의미하므로 터뜨려야할 블록을 체크할 때 -1은 예외처리 해주었다.
결론
보드를 우측으로 90도 회전하여, 블록이 터지면 위에서 아래로 블록이 체워지는게 아니라 우측에서 좌측으로 채워지도록 하여, 큐의 개념을 활용하여 구현했다.
보드를 돌면서 4개가 붙어있는 경우 좌표를 저장하고, 더 이상 터뜨릴 블록이 없을 때 까지 반복하며, 블록을 터트리고 빈자리를 -1로 채우는 과정을 반복한다.
블록이 터질 때 마다 횟수를 카운트하여 반환하면 끝
👨💻 소스 코드
def solution(m, n, board): answer = 0 newBoard = [] for i in range(n): temp = [] for j in range(m - 1, -1, -1): temp.append(board[j][i]) newBoard.append(temp) while True: boom = set() for i in range(1, n): for j in range(1, m): if newBoard[i - 1][j - 1] == newBoard[i - 1][j] == newBoard[i][j - 1] == newBoard[i][j] != -1: boom |= {(i, j), (i - 1, j - 1), (i - 1, j), (i, j - 1)} if not boom: break for i, j in boom: newBoard[i][j] = 0 for i in range(n): newBoard[i] = [item for item in newBoard[i] if item != 0] for k in range(m - len(newBoard[i])): newBoard[i].append(-1) answer += 1 return answer
Author And Source
이 문제에 관하여([프로그래머스 Level2] 프렌즈4블록), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@choiyunh/프로그래머스-Level2-프렌즈4블록저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)