[PS] BOJ 29721 / 변형 체스 놀이 : 다바바(Dabbaba)

Minjun Kim

10 Jul 2025 • 1 min read

문제 링크: https://www.acmicpc.net/problem/29721

Thumbnail: Photo by Daniel Stiel (Unsplash)

맵을 활용하는 문제였습니다.

풀이

체스판 전체를 배열로 관리하려고 하기보단 Map 자료구조를 활용해 방문한/이미 기물이 위치한 위치를 저장하는 편이 유리합니다.

먼저 모든 기물의 위치를 저장한 뒤, 각 기물의 위치에서 이동 가능한 모든 위치에 대해 해당 위치에 다른 기물이 있거나 이미 방문하지 않았는지 확인하면 됩니다.

전체 코드

input = open(0).readline
N, K = map(int, input().split())

visited = {}
dabbabas = []

for i in range(K):
    x, y = map(lambda n: int(n) - 1, input().split())
    visited[(x, y)] = True
    dabbabas.append((x, y))

cnt = 0
for x, y in dabbabas:
    for dx, dy in ((2, 0), (0, 2), (0, -2), (-2, 0)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < N and 0 <= ny < N and not visited.get((nx, ny), False):
            cnt += 1
            visited[(nx, ny)] = True

print(cnt)

solution.py