BOJ 16918 _ 봄버맨 _ 파이썬

📃 문제

백준 16918번 마인크래프트

알고리즘 - 구현, 그래프 탐색

문제 요약

첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다.
초기 배치가 빈 칸은 '.'로, 폭탄은 'O'로 주어진다.

1) 0초 : 초기 값
2) 1초 후 : 아무것도 하지 않는다
3) 또 1초 후: 빈 칸이던 칸에 폭탄을 설치한다 == 모든 칸에 폭탄이 있게된다
4) 또 1초 후: 3초전에 폭탄이 있던 곳이 터진다. -> 인접폭탄(상하좌우)까지 터진다
그 이후 1초마다 3),4)를 반복한다

예제 해석

.......
...O...
....O..
.......
OO.....
OO.....
<초기 상태, 1초 후>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
<2초 후>

OOO.OOO
OO...OO
OOO...O
..OO.OO
...OOOO
...OOOO
<3초 후>

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
<4초 후>

.......
...O...
....O..
.......
OO.....
OO.....
<5초 후>

다음과 같은 규칙을 발견할 수 있다.

• 폭탄 배치는 3초부터 4초마다 동일하다.
  즉, 3초 후==7초 후 , 4초 후 == 8초 후
  ⚠️ 1초의 상태는 규칙에 포함하면안된다!! 예외있음
• 매 짝수 초에는 모든 칸이 폭탄이다.

💡 시도 과정

arr : 초기 입력 상태

n == 1 이면 아무 것도 하지 않았기 때문에 arr 그대로 출력한다.
n이 짝수이면, 모든 칸을 폭탄(0)으로 채워서 출력한다.

n이 홀수이면, 3초부터 4초마다(n%4== 3)의 경우와, 5초부터 4초마다(n%4== 1)의 경우 두가지로 나뉜다.
5초의 결과도 3초의 결과에 따라 종속되기 때문에 3초의 경우를 먼저 구한다.

1) 시간초과 😵

모든 좌표를 저장한 배열 all을 만들고, 초기 상태에 있던 폭탄이 터질 경우 .이 되는 자표들을 init배열에 넣는다.
all 배열에서 init 배열을 빼면 3초에 폭탄으로 남아있는 좌표들을 구할 수 있다(rest배열)

n%4 ==3 이라면 좌표중 rest배열에 있는 좌표엔 0(폭탄), 없는 곳엔 .(빈칸)으로 출력한다.

n%4 ==1 이라면 rest에 대해서 한번 더 작업해야한다.

# 봄버맨

import sys
input = sys.stdin.readline
from collections import deque

r, c, n = map(int,input().split())
arr = [list(input().rstrip()) for _ in range(r)]

if n==1: # 초기와 동일
    for li in arr:
        print(''.join(li))
elif n%2 == 0 :  # 짝수 초일 땐 다채워짐
    for _ in range(r):
        for _ in range(c):
            print('O',end='')
        print('')
else:
    all = [(i,j) for i in range(r) for j in range(c)]
    queue = deque([]) # 초기위치가 터지면 . 이될 위치들 저장
    init = []
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    for i in range(r):
        for j in range(c):
            if arr[i][j] == 'O':
                if (i,j) not in init:
                    init.append((i,j))
                for d in range(4):
                    if 0<=i+dy[d]<r and 0<=j+dx[d] < c:
                        if (i+dy[d], j+dx[d]) not in init:
                            init.append((i+dy[d], j+dx[d]))
    rest = list(set(all) - set(init))
    
    queue = deque(sorted(queue))

    if n%4 == 3:
        arr = [['.' for _ in range(c)] for _ in range(r)]
        for ri, rj in rest:
            arr[ri][rj] = 'O' 
        for li in arr:
            print(''.join(li))
    else: # n%4 ==1
        arr = [['O' for _ in range(c)] for _ in range(r)]
        for ri, rj in rest:
            if arr[ri][rj] != '.':
                arr[ri][rj] = '.'
            for d in range(4):
                if 0<=ri+dy[d]<r and 0<=rj+dx[d] < c:
                    if arr[ri+dy[d]][rj+dx[d]] != '.':
                        arr[ri+dy[d]][rj+dx[d]] = '.'

        for li in arr:
            print(''.join(li))

2) 정답 😍

visited로 방문여부 확인후 append

import sys
input = sys.stdin.readline
from collections import deque

r, c, n = map(int,input().split())
arr = [list(input().rstrip()) for _ in range(r)]
if n==1: # 초기와 동일
    for li in arr:
        print(''.join(li))
elif n%2 == 0 :  # 짝수 초일 땐 다채워짐
    for _ in range(r):
        for _ in range(c):
            print('O',end='')
        print('')
else:
    all = [(i,j) for i in range(r) for j in range(c)]
    visited = [[0 for _ in range(c)] for _ in range(r)]
    init = []
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    for i in range(r):
        for j in range(c):
            if arr[i][j] == 'O':
                if visited[i][j] == 0:
                    init.append((i,j))
                    visited[i][j] = 1
                for d in range(4):
                    if 0<=i+dy[d]<r and 0<=j+dx[d] < c:
                        if visited[i+dy[d]][j+dx[d]] == 0 :
                            init.append((i+dy[d], j+dx[d]))
                            visited[i+dy[d]][j+dx[d]] = 1
    rest = list(set(all) - set(init))
    
    if n%4 == 3:
        arr = [['.' for _ in range(c)] for _ in range(r)]
        for ri, rj in rest:
            arr[ri][rj] = 'O' 
        for li in arr:
            print(''.join(li))
    else: # n%4 ==1
        visited = [[0 for _ in range(c)] for _ in range(r)]
         # 3초에서 폭탄터지고 살아남은 폭탄들이 터진다면 . 이될 위치들 저장
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        arr = [['O' for _ in range(c)] for _ in range(r)]
        for ri, rj in rest:
            if arr[ri][rj] != '.':
                arr[ri][rj] = '.'
            for d in range(4):
                if 0<=ri+dy[d]<r and 0<=rj+dx[d] < c:
                    if arr[ri+dy[d]][rj+dx[d]] != '.':
                        arr[ri+dy[d]][rj+dx[d]] = '.'
        for li in arr:
            print(''.join(li))
            

반례코드

3 3 5
.O.
OO.
...

>>
OOO
OO.
O..

input6

6 7 6
OOOOOOO
OOOOOOO
OOOOOOO
OOOO.OO
OOOOOOO
OOOOOOO

output6

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO