티스토리 뷰
반응형
백준 16918번 봄버맨 (Python)
문제
● 문제 설명
봄버맨은 R×C 크기의 격자 위에서 폭탄을 설치하며 게임을 진행합니다.
각 칸은 폭탄(`O`)이 있거나 비어(`.`) 있을 수 있습니다.
폭탄의 작동 방식은 다음과 같습니다.
- 설치 후 3초가 지나면 폭발합니다.
- 폭발 시, 해당 칸과 상하좌우 4칸이 파괴되어 빈 칸(`.`)이 됩니다.
- 인접 폭탄이 함께 터지는 연쇄 폭발은 일어나지 않습니다.
- 폭발 후에는 즉시 새로운 폭탄을 설치할 수 있습니다.
봄버맨은 다음과 같은 행동 순서를 반복합니다.
- 초기 상태에서 일부 칸에 폭탄이 설치되어 있음.
- 1초 동안 아무 일도 일어나지 않음.
- 그다음 1초 동안 모든 빈 칸에 폭탄을 설치함 → 전부 `O`.
- 1초가 지나면 3초 전에 설치된 폭탄이 동시에 폭발함.
- 3–4 과정을 계속 반복함.
주어진 입력으로 N초가 지난 뒤 격자 상태를 출력해야 합니다.
● 테스트 케이스
입력 예시 1
6 7 3
.......
...O...
....O..
.......
OO.....
OO.....
출력 예시 1
OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO
입력 예시 2
6 7 4
.......
...O...
....O..
.......
OO.....
OO.....
출력 예시 2
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
입력 예시 3
6 7 5
.......
...O...
....O..
.......
OO.....
OO.....
출력 예시 3
.......
...O...
....O..
.......
OO.....
OO.....
● 문제 작동 원리
봄버맨은 시간에 따라 격자의 폭탄이 폭발하고 다시 설치되는 주기적 패턴을 가집니다.
즉, 격자는 4초마다 순환 주기를 가지며,
폭발 패턴은 두 종류(`3초 후`, `5초 후`)가 번갈아 반복됩니다.
예제 1의 경우,
- 3초 후 패턴은 `OOO.OOO` 등으로 바뀌었고,
- 5초 후에는 우연히 초기 상태와 같은 형태로 복귀합니다.
하지만, 이는 대칭 구조 덕분에 생긴 특수한 케이스로,
모든 입력에서 반드시 동일하게 복귀한다고 단정할 수는 없습니다.
문제 아이디어
문제의 핵심은 실제 시뮬레이션을 전부 하지 않고,
패턴의 주기성을 이용하여 N초 뒤 상태를 빠르게 도출하는 것입니다.
다음 규칙을 사용합니다.
이를 위해,
arr
: 초기 입력 상태arr2
: 첫 번째 폭발 후 상태 (3초 때)arr3
: 두 번째 폭발 후 상태 (5초 때)
를 순서대로 계산합니다.
두 폭발 상태를 모두 구해두면,
N값에 따라 바로 정답을 출력할 수 있습니다.
전체코드
def Print(arr,R,C):
for i in range(R):
for j in range(C):
print(arr[i][j],end='')
print()
R,C,N= map(int,input().split())
arr=[]
arr2=[ ['O' for _ in range(C)] for _ in range(R)]
arr3=[ ['O' for _ in range(C)] for _ in range(R)]
dx=[1,0,-1,0]
dy=[0,1,0,-1]
for i in range(R):
arr.append(list(input()))
for i in range(R):
for j in range(C):
if arr[i][j]=='O':
arr2[i][j]='.'
for a,b in zip(dx,dy):
x=i+a
y=j+b
if 0<=x
결론
이 코드는 시간 주기의 반복성을 이용하여,
폭탄의 폭발 과정을 효율적으로 계산한 풀이입니다.
arr2
: 첫 번째 폭발(3초 후) 상태arr3
: 두 번째 폭발(5초 후) 상태- 그 이후에는 4초 주기로 패턴이 반복되므로
- N값의 나머지(`%4`)에 따라 정답이 바로 결정됩니다.
예제 입력에서는 5초 후 상태
가 초기와 우연히 동일하지만,
그것은 대칭적 폭탄 배치로 인한 특수 사례이며,
다른 입력에서는 두 번째 폭발(`arr3`)이 초기 상태와 달라질 수 있습니다.
즉,
이 풀이 방식은 모든 케이스에 대해 안전하게 작동하는 일반해입니다.
반응형
'백준 스터디' 카테고리의 다른 글
백준 1120번 문자열 Python (0) | 2025.10.10 |
---|---|
백준 16234 인구 이동 Python (0) | 2025.10.09 |
백준 1094번 막대기 Python (0) | 2025.10.07 |
백준 2665번 미로만들기 Python (0) | 2025.10.07 |
백준 1059 좋은 구간 (Python) (0) | 2025.10.06 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- c언어
- 알고리즘기초
- DP
- 그래프 탐색
- 문제 풀이
- 파이썬
- 그리디알고리즘
- 파이썬문제풀이
- 알고리즘문제풀이
- 코딩테스트
- 문자열처리
- c++알고리즘
- 백준
- C++
- 알고리즘 문제풀이
- 파이썬코딩
- 그리디
- Python
- 문제풀이
- 코딩 테스트
- 프로그래밍
- 동적계획법
- dfs
- 동적 계획법
- 알고리즘
- 객체지향
- 브루트포스
- python 알고리즘
- 코딩
- C++ 알고리즘
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |
글 보관함
반응형