티스토리 뷰
문제 설명
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
- solution 함수의 인자로, 2차원 배열인 game_board와 table이 주어집니다.
- game_board의 0은 빈 공간, table의 1은 블럭이 있는 칸입니다.
- game_board의 빈 공간에 table의 블럭을 채워야 합니다.
- table의 블럭들은 뒤집기를 제외하고 회전이 가능합니다.
- 블럭을 한 번에 하나씩만 넣을 수 있고, 보드에 새로 채워 넣은 블럭과 인접한 칸이 비어 있으면 안 됩니다. 즉, 빈 공간과 채워질 블럭의 모양이 딱 맞아야 함! 2개의 블럭을 조합하여 하나의 공간을 채운다는 것이 불가능합니다. (이해 안 된다면 사진 참고)
이 때, 보드에 퍼즐을 최대한 많이 채워 넣고, 총 몇 칸이 채워졌는지 반환하는 solution 함수를 작성하면 됩니다!
하하!
이 글을 보시는 분들 중, 이 문제를 처음부터 끝까지 진심으로 혼자서 푸신 분이 있으시다면 연락 부탁드립니다. (for real)
부디 소인을 제자로 받아주십시오.
DFS/BFS로 분류되어 있으나 알고리즘의 기여는 10%도 안 되고요. 거의 쌩 구현 문제입니다.
풀이 과정
우선 해야할 작업을 수도 코드마냥 적어 본다면 다음과 같을 겁니다.
1. game_board에서 빈 공간 좌표 찾기
2. table에서 블럭의 좌표 찾기
3. 찾은 블럭을 돌려가며 빈 공간과 모양이 일치하는지 확인하기 << how?
4. 일치한다면, 블럭의 크기를 answer에 더하기
모든 빈 공간에 대해 모든 블럭을 확인할 때까지 3, 4번을 반복.
1, 2번은 DFS/BFS 알고리즘을 통해 찾을 수 있을 것 같지만, 3번은 도무지 방법이 떠오르지 않았습니다.
좀 보다가 ... 고작 1달 정도 공부한 저의 뇌로는 말이 안 되는 것 같아서 바로 검색해 봤습니다.
https://eunbin00.tistory.com/190
[프로그래머스] 퍼즐조각 채우기 (Python, BFS, 구현)
🌱 문제 BFS/DFS 문제이지만 개인적으로 BFS 찔끔 쓰고, 완전 빡쎈 구현인 것 같았던.. 문제입니다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤
eunbin00.tistory.com
그리하여 이번 문제는 어떠한 저의 풀이가 아닌,
이분의 코드를 보며 감탄하며 이해하는 것
을 목표로 두었습니다. 은빈?님... 정말 감사합니다.
정답 코드 이해 과정
1) find_space 함수
우선 2번까지는 BFS를 통해 구해 보겠습니다.
# board에서 number가 적힌 좌표를 리스트에 담아 반환하는 함수
# game_board의 경우 빈 공간을 찾아야 하니까 number가 0이 되고
# table의 경우 블럭이 차지하는 공간을 찾아야 하니까 number가 1이 된다
def find_space(board, number):
row = len(board)
col = len(board[0])
# 상하좌우 탐색을 위한 dx, dy 생성
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# board의 각 칸의 방문 여부를 저장할 visited 생성
visited = [[False] * col for _ in range(row)]
# 반환될 리스트
total_space_list = []
# 2차원 배열 board 순회
for i in range(row):
for j in range(col):
# 이전에 방문하지 않았고, number가 적힌 칸이라면
if not visited[i][j] and board[i][j] == number:
# 큐를 생성하여 (i,j) 튜플 형태로 추가
queue = deque([(i, j)])
# XOR 연산을 통해 해당 칸의 값을 변경 (number가 0이면 1, 1이면 0으로)
board[i][j] = number ^ 1
# 방문 처리
visited[i][j] = True
# 큐를 통해 탐색된 좌표를 담을 리스트 <- 하나의 덩어리가 담김
space_list = [(i, j)]
# 큐가 비어 있지 않다면 반복
while queue:
# 큐 pop
x, y = queue.popleft()
# pop한 좌표의 상하좌우 탐색
for _ in range(4):
nx, ny = x + dx[_], y + dy[_]
# nx, ny 값이 유효한 좌표이고, number가 적힌 칸이라면
if 0 <= nx < row and 0 <= ny < col and board[nx][ny] == number:
# 큐에 추가
queue.append((nx, ny))
# 칸에 적힌 값 변경
board[nx][ny] = number ^ 1
# 방문 처리
visited[nx][ny] = True
# 현재 리스트에 좌표로 추가
space_list.append((nx, ny))
# 2차원 리스트에 추가 <- 여러 덩어리가 담김
total_space_list.append(space_list)
return total_space_list참고로 여기서 '덩어리(...)'라고 표현한 것들은,
이렇게 하나의 블럭, 또는 하나의 빈 공간을 뜻합니다.
while 문을 통해 이 덩어리를 이루는 좌표 (nx, ny)들을 찾아냅니다.
결론적으로 space_list에는 한 덩어리를 이루는 여러 좌표들이 1차원 배열로 담기고,
total_space_list 에는 여러 개의 덩어리가 담긴 2차원 배열이 담기는 것입니다.
2) make_table 함수
그렇지만 사실 이 데이터로는 game_board와 table을 비교하기가 어렵습니다. 인덱스의 기준이 game_board, table에 있기 때문입니다. 쉬운 비교를 위해서는 빈 공간과 블럭의 '독립적인 좌표'가 필요합니다.
이렇게 말입니다. 이를 make_table이라는 함수로 구현합니다.
# block의 독립적인 좌표를 만들어 주는 함수
def make_table(block):
x, y = zip(*block) # 파이썬의 unpacking(*)을 사용하여 block 리스트의 각 요소를 분해 후, zip으로 동일한 인덱스의 요소끼리 묶어서 튜플로 반환
row, col = max(x) - min(x) + 1, max(y) - min(y) + 1 # 해당 블럭의 크기에 딱 맞는 row, col 값을 구한다
table = [[0] * col for _ in range(row)] # block 크기에 맞는 테이블을 0으로 초기화
# block의 (x,y) 값 순회
for i, j in block:
# x는 최솟값만큼 빼서 위쪽으로 이동시키고
i = i - min(x)
# y는 최솟값만큼 빼서 왼쪽으로 이동시켜 독립적인 좌표를 만든다
j = j - min(y)
# 해당 좌표에 1을 넣음으로써 차지하는 칸 표시
table[i][j] = 1
return table함수의 인자에 * 표시를 붙여서 리스트를 각 요소로 분해하는 것을 언패킹, 함수의 정의 부분에서 파라미터에 * 표시를 붙여서 가변 인자들을 하나의 리스트로 묶는 것을 패킹이라고 합니다. 솔직히 파이썬에 이런 문법이 있는지 처음 알았습니다.
3) rotate 함수
빈 공간과 블럭 공간의 독립적인 좌표를 얻었으니, 이제 각 좌표가 같은지 비교해 보면 될 것입니다.
그렇지만 블럭을 회전시켰을 때 같은 경우도 고려해야 하기 때문에 블럭을 오른쪽으로 90도씩 돌려주는 rotate 함수를 구현하겠습니다.
# table을 오른쪽으로 90도 회전한 좌표와 블럭의 크기를 반환하는 함수
def rotate(table):
# table의 row와 col을 계산
row = len(table)
col = len(table[0])
# 오른쪽으로 90도 돌리면 row와 col의 크기가 교체되기 때문에 col*row 크기인 rotate을 생성
rotate = [[0] * row for _ in range(col)]
# 블럭의 크기를 카운트할 변수 생성
count = 0
# row*col 크기의 table을 순회
for i in range(row):
for j in range(col):
# 블럭이 있는 칸이면
if table[i][j] == 1:
# 카운트 증가
count += 1
# table의 (i,j) 좌표를 오른쪽으로 90도 회전하면 rotate의 (j,row-1-i) 좌표로 이동
rotate[j][row - 1 - i] = table[i][j]
return rotate, counttable의 (i, j) 좌표를 회전하면 rotate의 (j, row-1-i) 좌표가 된다는 점은 직접 그려서 이해하시는 게 좋을 것 같습니다.
저도 그렇게 이해했습니다.
만약에 저 혼자 어떻게 make_table까지 구현했다 해도, j가 row-1-i로 변한다는 규칙을 못 구해서 막혔을 것으로 추정됩니다.
다들 규칙을 어떻게 그렇게 잘 찾으시는 겁니까?
4) 최종 solution 함수
대망의 solution 함수를 보시겠습니다.
from collections import deque
# board에서 number가 적힌 좌표를 리스트에 담아 반환하는 함수
# game_board의 경우 빈 공간을 찾아야 하니까 number가 0이 되고
# table의 경우 블럭이 차지하는 공간을 찾아야 하니까 number가 1이 된다
def find_space(board, number):
row = len(board)
col = len(board[0])
# 상하좌우 탐색을 위한 dx, dy 생성
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# board의 각 칸의 방문 여부를 저장할 visited 생성
visited = [[False] * col for _ in range(row)]
# 반환될 리스트
total_space_list = []
# 2차원 배열 board 순회
for i in range(row):
for j in range(col):
# 이전에 방문하지 않았고, number가 적힌 칸이라면
if not visited[i][j] and board[i][j] == number:
# 큐를 생성하여 (i,j) 튜플 형태로 추가
queue = deque([(i, j)])
# XOR 연산을 통해 해당 칸의 값을 변경 (number가 0이면 1, 1이면 0으로)
board[i][j] = number ^ 1
# 방문 처리
visited[i][j] = True
# 큐를 통해 탐색된 좌표를 담을 리스트 <- 하나의 덩어리가 담김
space_list = [(i, j)]
# 큐가 비어 있지 않다면 반복
while queue:
# 큐 pop
x, y = queue.popleft()
# pop한 좌표의 상하좌우 탐색
for _ in range(4):
nx, ny = x + dx[_], y + dy[_]
# nx, ny 값이 유효한 좌표이고, number가 적힌 칸이라면
if 0 <= nx < row and 0 <= ny < col and board[nx][ny] == number:
# 큐에 추가
queue.append((nx, ny))
# 칸에 적힌 값 변경
board[nx][ny] = number ^ 1
# 방문 처리
visited[nx][ny] = True
# 현재 리스트에 좌표로 추가
space_list.append((nx, ny))
# 2차원 리스트에 추가 <- 여러 덩어리가 담김
total_space_list.append(space_list)
return total_space_list
# block의 독립적인 좌표를 만들어 주는 함수
def make_table(block):
x, y = zip(*block) # 파이썬의 unpacking(*)을 사용하여 block 리스트의 각 요소를 분해 후, zip으로 동일한 인덱스의 요소끼리 묶어서 튜플로 반환
row, col = max(x) - min(x) + 1, max(y) - min(y) + 1 # 해당 블럭의 크기에 딱 맞는 row, col 값을 구한다
table = [[0] * col for _ in range(row)] # block 크기에 맞는 테이블을 0으로 초기화
# block의 (x,y) 값 순회
for i, j in block:
# x는 최솟값만큼 빼서 위쪽으로 이동시키고
i = i - min(x)
# y는 최솟값만큼 빼서 왼쪽으로 이동시켜 독립적인 좌표를 만든다
j = j - min(y)
# 해당 좌표에 1을 넣음으로써 차지하는 칸 표시
table[i][j] = 1
return table
# table을 오른쪽으로 90도 회전한 좌표와 블럭의 크기를 반환하는 함수
def rotate(table):
# table의 row와 col을 계산
row = len(table)
col = len(table[0])
# 오른쪽으로 90도 돌리면 row와 col의 크기가 교체되기 때문에 col*row 크기인 rotate을 생성
rotate = [[0] * row for _ in range(col)]
# 블럭의 크기를 카운트할 변수 생성
count = 0
# row*col 크기의 table을 순회
for i in range(row):
for j in range(col):
# 블럭이 있는 칸이면
if table[i][j] == 1:
# 카운트 증가
count += 1
# table의 (i,j) 좌표를 오른쪽으로 90도 회전하면 rotate의 (j,row-1-i) 좌표로 이동
rotate[j][row - 1 - i] = table[i][j]
return rotate, count
def solution(game_board, table):
answer = 0
# game_board에서 빈 공간 찾기
empty_space_list = find_space(game_board, 0)
# table에서 블럭이 차지하는 공간 찾기
block_space_list = find_space(table, 1)
# 모든 빈 공간을 확인
for empty_space in empty_space_list:
# 이중 for문을 탈출하기 위한 변수
is_filled = False
# 빈 공간의 독립적인 좌표 생성
empty_table = make_table(empty_space)
# 모든 블럭 공간을 확인
for block_space in block_space_list:
# 블럭 공간의 독립적인 좌표 생성
block_table = make_table(block_space)
# 90도 회전한 모양부터 360도 회전한 모양까지 확인하기 위해 4번 반복
for _ in range(4):
# 오른쪽으로 90도 회전한 블럭과 해당 블럭의 크기를 구함
block_table, count = rotate(block_table)
# 해당 블럭과 빈 공간이 딱 맞다면
if empty_table == block_table:
# answer에 블럭의 크기를 더함
answer += count
# 해당 블럭은 사용 완료했으니 리스트에서 아예 제거
block_space_list.remove(block_space)
# 이중 for문 한번에 탈출 시도
is_filled = True
break
# 이중 for문 탈출
if is_filled:
break
return answersolution 함수를 작성하며 얻은 깨달음은, block_table을 rotate한 결과를 다시 block_table에 넣음으로써 오른쪽으로 90도 회전된 블럭을 다음 번에 또 90도 돌려서 180도 회전된 블럭을, 그 다음에는 270도, 마지막 4번째에는 360도 회전하여 4가지 버전을 다 확인할 수 있게끔 구현했다는 것입니다.
어떻게 이런 생각을...
느낀 점
rotate랑 make_table 함수가 핵심인 것 같은데, 제 주석을 제외하면 짧은 함수라 풀어보지 않으신 분들은 나름 쉽다고? 생각하실 수도 있을 것 같습니다. 그렇지만 제 생각에는 스텝별로 생각한 해결책을 코드로 구현해내는 능력과 아이디어가 중요한 문제였던 것 같습니다. 정말 천재 같습니다. 왜 그렇게 기업들이 코드로 구현해내는 능력을 중요시하는지 알 것도 같네요.
저도 열심히 하다보면 이런 문제도 코웃음 치며 풀 수 있는 날이 올까요?
물론입니다.
아마 이 글이 여태 업로드 한 글 중에 가장 열심히 적은 글인 것 같네요.
계속 정진하겠습니다~
모두 건강하시고 행복하시길 바랍니다.
'Algorithm' 카테고리의 다른 글
| 백준 1939번: 중량제한 (G3) - Python 풀이 (0) | 2025.02.18 |
|---|---|
| 백준 2110번: 공유기 설치 (G4) - Python 풀이 (0) | 2025.02.17 |
| 백준 3079번: 입국심사 (G5) - Python 풀이 (1) | 2025.02.14 |
| 백준 2606번: 바이러스 (S3) - Python 풀이 (0) | 2025.02.08 |
| 프로그래머스 Lv.3: 종이 삼각형 - Python 풀이 (0) | 2025.02.05 |
- Total
- Today
- Yesterday
- 우선순위큐
- Swift
- 자료구조
- 프로그래머스
- 다익스트라
- 스택
- 알고리즘
- Baekjoon
- 코테준비
- 그리디
- ios
- SQL
- 큐
- swea
- Python
- dp
- ios앱개발
- 구현
- 백준
- 코테
- Deque
- 투포인터
- Programmers
- MySQL
- 이분탐색
- 정렬
- Swift로백준풀기
- 다이나믹프로그래밍
- 코딩테스트
- 힙
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 |