[알고리즘/구현] 16918번 : 봄버맨 - python

링크 : https://www.acmicpc.net/problem/16918

---

• 문제
• 소요시간: 1시간 26초

---

• 설계하기(접근방법) 

1. 입력받기

격자판을 입력받으면서 숫자(초)로 바꿔준다

 

2. 구현하기

while문을 통해 시간동안 시뮬레이션을 실행한다.

+ 아래의 코드로 수정했다.

 

3. 출력하기

숫자를 다시 문자로 바꾸어주어 출력한다.

 

---

• 코드(출력)

x, y , time = map(int,input().split())
vec = []
field = [[0 for i in range(y)] for _ in range(x)]

for _ in range(x):
    vec.append(input())


# 폭탄 시간으로 변환 
for i in range(x):
    for j in range(y):
        if vec[i][j] == '.':
            pass
        else:
            field[i][j] += 2

time -= 1
cnt = 0

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

while time:
    # 폭탄 시간 감소
    for i in range(x):
        for j in range(y):
            if field[i][j] == 3 or field[i][j] == 2:
                field[i][j] -= 1
            elif field [i][j] == 1:
                field[i][j] = 0
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    if 0 <= nx < x and 0 <= ny < y:
                        if field[nx][ny] == 1:
                            pass
                        else:
                            field[nx][ny] = 0
            else:
                pass
    # 2초에 1번씩 폭탄 설치
    if cnt % 2 == 0:
        for i in range(x):
            for j in range(y):
                if field[i][j] == 0:
                    field[i][j] = 3
    cnt += 1
    time -= 1 

for i in range(x):
    for j in range(y):
        if field[i][j] == 0:
            print('.', end = '')
        else:
            print('O', end = '')
    print()

NEW VER.

x, y, time = map(int, input().split())
vec = [list(input()) for _ in range(x)]

# 폭발과 설치를 시뮬레이션하기 위한 방향 설정
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# time이 1이면 초기 상태 그대로 출력
if time == 1:
    for row in vec:
        print(''.join(row))
    exit()

# 짝수 초에는 모든 칸에 폭탄이 채워지므로 바로 출력 가능
if time % 2 == 0:
    for _ in range(x):
        print('O' * y)
    exit()

# 3초 또는 5초일 때의 상태 구하기
def get_bomb_state():
    bomb = [['O'] * y for _ in range(x)]
    
    for i in range(x):
        for j in range(y):
            if vec[i][j] == 'O':  # 기존 폭탄이 있던 위치는 터짐
                bomb[i][j] = '.'
                for k in range(4):  # 상, 하, 좌, 우 폭발
                    ni, nj = i + dx[k], j + dy[k]
                    if 0 <= ni < x and 0 <= nj < y:
                        bomb[ni][nj] = '.'
    return bomb

# 3초 후 상태
state_3_sec = get_bomb_state()

# 5초 후 상태는 3초 후 폭탄을 기반으로 다시 계산
vec = state_3_sec
state_5_sec = get_bomb_state()

# time이 3초면 3초 후 상태, 5초면 5초 후 상태를 출력
result = state_3_sec if time % 4 == 3 else state_5_sec
for row in result:
    print(''.join(row))

---

• 얻어갈 부분

1. 시간이 오래 걸려서 다른 사람의 코드를 보니, 짝수초에는 항상 폭탄이 채워지고, 홀수일 때 터진다는 것을 알게되었다.

+ 3, 5초 후의 상태가 계속 같은 주기로 반복이 된다. 즉 시뮬레이션 필요없이 케이스 몇 개만 구하면 되는 문제다.