목차
👀, 🤷♀️ , 📜
이 아이콘들을 누르시면 코드, 개념 부가 설명을 보실 수 있습니다:)
프렌즈 4블록
난이도 | ★★★
문제
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다.
이번에 출시할 게임 제목은 “프렌즈4블록”. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
만약 판이 이와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워 진다.
같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.
블록이 지워진 후에 위에 있는 블록이 아래로 떨어져빈 공간을 채우게 된다.
만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.
위 초기 배치를 문자로 표시하면 아래와 같다.
TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ
각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C) 을 의미한다. 입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.
[입력 형식]
- 입력으로 판의 높이 m , 폭 n 과 판의 배치 정보 board 가 들어온다.
- 2 ≦ n , m ≦ 30
- board 는 길이 n 인 문자열 m 개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
[출력 형식]
- 입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
[입출력 예제]
[예제에 대한 설명]
- 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4 개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
- 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.
풀이과정
풀이는 3단계로 구성되어 있으며 비즈니스 로직을 구현해야 한다.
게임 요구 사항을 구현해보는 문제로, 어려운 문제는 아니지만 구현해야 할 비즈니스 로직이 상당히 복잡한 문제다.
1️⃣ 일치 여부를 찾기
2️⃣ 일치한 위치를 삭제(여기서는 # 으로 처리)
3️⃣ 빈 공간에 위에 있는 블록을 아래로 떨어뜨리는 처리
이렇게 3가지 로직이다.
그럼
위의 경우로 예를 들어 설명해보겠다
0. 중첩 리스트 Nested List 표현
먼저 단계별로 처리하기 전, 처리를 쉽게 하기 위해 board로 넣어보겠다!
- 문자열을 문자 단위 리스트로 분리하여 중첩 리스트 Nested List 표현
# 리스트 안에 리스트가 들어가 있으므로 중첩 리스트이다
# [list(x)]
board = [list(x) for x in board]
1. 일치 여부 판별
먼저 지워지는 조건을 다시보자.
- 블록이 2×2 형태로 4개가 붙어있을 경우
- 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다
어렵게 생각할 것 없이 이 조건 그래도 구현하면 된다.
그런데 코드가 딱 보기 힘드니 세부적인 과정을 알려주고 전체적인 과정을 보려주겠다.
먼저 각 if문에서의 처리는 아래와 같다
👀코드 보기
for i in range(m - 1):
for j in range(n - 1):
# 이 코드가 2x2의 네모 범위 내에 존재하는 것들이 같은지를 물어보는 것이다
# != '#' 얘는 찾은 네모가 이미 찾은게 아닌지를 물어보는것이다
## 안찾은것만 넣어야 하니(#을 넣지 말아야하니) #이 아닌 때만 추가해 주는 것이다
if board[i][j] == board[i][j + 1] == board[i + 1][j + 1] == board[i + 1][j] != '#':
matched.append([i, j])
그럼 이제 이 2x2 if문 처리를 한 뭉텅이로 보고 전체 1번 코드를 돌아보겠다!
👀코드 보기
matched = True
while matched:
# 1) 일치 여부 판별
matched = []
for i in range(m - 1):
for j in range(n - 1):
# 이 코드가 2x2의 네모 범위 내에 존재하는 것들이 같은지를 물어보는 것이다
# != '#' 얘는 찾은 네모가 이미 찾은게 아닌지를 물어보는것이다
## 안찾은것만 넣어야 하니(#을 넣지 말아야하니) #이 아닌 때만 추가해 주는 것이다
if board[i][j] == board[i][j + 1] == board[i + 1][j + 1] == board[i + 1][j] != '#':
matched.append([i, j])
2. 일치한 위치 삭제
이 단계에서 아까 모아둔 조건을 만족하는 match의 좌표를 #으로 바꿔주기만 하면 된다
👀코드 보기
for i, j in matched:
board[i][j] = board[i][j + 1] =
board[i + 1][j + 1] = board[i + 1][j] = '#'
3. 빈공간 블럭 처리
’#’이라는 빈 부분 [i + 1][j] 이 있으면 위의 비지 않은 부분board[i][j]과 바꿔준다
👀코드 보기
# 3) 빈공간 블럭 처리
for _ in range(m):
for i in range(m - 1):
for j in range(n):
# '#'이라는 빈 부분 ```[i + 1][j]``` 이 있으면 위의 비지 않은 부분```board[i][j]```과 바꿔준다
if board[i + 1][j] == '#':
board[i + 1][j], board[i][j] = board[i][j], '#'
➕ 참고로 이 예시에선 안나왔지만 for _ in range(m):이게 있는 이유는 ‘맨 위부터 아래까지 내려와야하는 경우도 있어야 하니까’이다.
4. 반복
처리 후 또 2X2가 나올 수 있기 때문에 matched가 더이상 없어 False가 될 때 까지 위의 1~3 과정을 반복한다.
5. 개수 세기
‘지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.’ 가 주어진 조건이므로,
return sum(x.count('#') for x in board)으로 ‘#’의 개수를 세면 답이 나온다
전체 코드
모든 비즈니스 로직을 구현한 전체 코드는 다음과 같다
def solution(m, n, board):
board = [list(x) for x in board]
matched = True
while matched:
# 1) 일치 여부 판별
matched = []
for i in range(m - 1):
for j in range(n - 1):
if board[i][j] == board[i][j + 1] == board[i + 1][j + 1] == board[i + 1][j] != '#':
matched.append([i, j])
# 2) 일치한 위치 삭제
for i, j in matched:
board[i][j] = board[i][j + 1] = board[i + 1][j + 1] = board[i + 1][j] = '#'
# 3) 빈공간 블럭 처리
for _ in range(m):
for i in range(m - 1):
for j in range(n):
# '#'이라는 빈 부분 ```[i + 1][j]``` 이 있으면 위의 비지 않은 부분```board[i][j]```과 바꿔준다
if board[i + 1][j] == '#':
board[i + 1][j], board[i][j] = board[i][j], '#'
return sum(x.count('#') for x in board)