-
[백준 11559] Puyo Puyo (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 22. 01:27
문제풀이
BFS를 이용한 구현문제이다. 주어진 조건만 잘 구현하면 쉽게 해결할 수 있다.
1. 뿌요 탐색 및 뿌요 부수기
- 현재 위치에서 동일한 색상의 뿌요가 4개 이상일 경우 뿌요를 부신다.
2. 1의 과정에서 없앤 뿌요가 있으면 뿌요를 내려준다.
- 없앤 뿌요가 없으면 더 이상 진행할 것이 없으므로 결과를 바로 출력한다.
코드 보면 쉽게(?) 이해할 수 있다.
코드
import sys from collections import deque dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] # BFS 를 통해 뿌실 뿌요 탐색 def bfs(x, y, color): global flag tmp_q = deque([(x, y)]) l = deque([(x, y)]) check = [[False] * 6 for _ in range(12)] check[x][y] = True while tmp_q: x, y = tmp_q.popleft() for k in range(4): nx, ny = x + dx[k], y + dy[k] if 0 <= nx < 12 and 0 <= ny < 6: if board[nx][ny] == color and not check[nx][ny]: check[nx][ny] = True tmp_q.append((nx, ny)) l.append((nx, ny)) # 동일 색의 뿌요가 4개 이상 붙어있을 경우 뿌요 부수기 if len(l) >= 4: while l: x, y = l.popleft() board[x][y] = '.' flag = True # 뿌요를 부신 후 남아있는 뿌요 내리기 def move_down(): i, j = 11, 5 while j >= 0: cnt = 0 while i >= 0: if board[i][j] == '.': cnt += 1 i -= 1 continue if not cnt: i -= 1 continue board[i + cnt][j] = board[i][j] board[i][j] = '.' i += cnt cnt = 0 j -= 1 i = 11 if __name__ == '__main__': board = [list(map(str, sys.stdin.readline().rstrip())) for _ in range(12)] q = deque() ans = 0 for i in range(12): for j in range(6): if board[i][j] == '.': continue q.append((i, j)) while q: size = len(q) flag = False # 없앤 뿌요가 있는지 여부 체크 for _ in range(size): x, y = q.popleft() # 이미 부신 뿌요는 탐색하지 않음 if board[x][y] == '.': continue color = board[x][y] # 뿌요 탐색 및 부수기 bfs(x, y, color) # 뿌요를 부셨다면 1 증가 if flag: ans += 1 # 부실 뿌요가 없다면 종료 else: print(ans) exit(0) # 뿌요 내리기 move_down() for i in range(12): for j in range(6): if board[i][j] == '.': continue q.append((i, j)) print(ans)
결과
문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!
'Algorithm & Problem Solving > 그래프 이론(DFS & BFS)' 카테고리의 다른 글
[백준 1939] 중량제한 (Python) (0) 2021.01.27 [백준 2589] 보물섬 (Python) (0) 2021.01.25 [백준 16947] 서울 지하철 2호선 (Python) (0) 2021.01.20 [백준 14226] 이모티콘 (Python) (0) 2020.12.15 [백준 14502] 연구소 (Python) (0) 2020.11.28