[백준] 16918 봄버맨 (실버1) / 구현, 시뮬레이션

문제요약

나의 코드 및 설명 01 (시간초과)

• 자꾸 시간초과가 발생했다. 이 방법 말고도 3~4가지 방법을 더 사용해봤는데 혼자 힘으로 시간초과를 극복하지 못했다. 
  격자판 입력받는 부분도 바꿔보고, n%4 == 3 일 때의 방문처리를 다른 방법으로 하는 등 소스들을 여러 번 수정해보았는데 계속 시간초과가 발생했다.

import sys

r, c, n = map(int,input().split()) #r*c격자판 #n초가 흐른 후의 격자판
board = [] 
for _ in range(r):
    board.append(list(sys.stdin.readline()))

check = []

for y in range(r):
    for x in range(c):
        if board[y][x] == "O":
            check.append((x,y))

#시간이 2의 배수일 경우 : 꽉찬 폭탄들
#0, 1, 5,... 초 일때 : 초기 폭탄
#3, 7, 11, ... 초 일때 : 초기 폭탄 터짐

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

if n != 0 and n % 2 == 0:
    line = "O"*c
    for _ in range(r):
        print(line)
elif n == 0 or n%4 == 1:
    for i in range(r):
        print("".join(map(str, board[i])))
elif n%4 == 3:
    v = []
    for y in range(r):
        for x in range(c):
            if (x,y) in check:
                board[y][x] = "."
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<c and 0<=ny<r:
                        board[ny][nx] = "."
                        v.append((nx, ny))
            elif ((x,y) not in check) and ((x,y) not in v):
                board[y][x] = "O"

    for i in range(r):
        print("".join(map(str, board[i])))

나의 코드 및 설명 02 (틀렸습니다)

• 결국 다른 사람의 코드를 힌트삼아 시간초과를 해결할 수 있었다.
• n%4 == 3 일 때, 결과 격자판을 출력할 bomb 라는 임시 리스트를 만들고, 원본 격자판 board 에서 폭탄이 있는 위치와 해당 위치의 상하좌우에 해당하는 좌표 값을 "."으로 바꿔주는 소스 코드를 작성했고, 시간초과를 극복할 수 있었다. 하지만 이번엔 틀렸다고 한다. 예제의 입력값들이 제대로 출력되는데 무엇이 문제인지 몰랐다. 

import sys

r,c,n = map(int, input().split())
board = []
for _ in range(r):
    board.append(list(input()))

#시간이 2의 배수일 경우 : 꽉찬 폭탄들
#0, 1, 5,... 초 일때 : 초기 폭탄
#3, 7, 11, ... 초 일때 : 초기 폭탄 터짐

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

if n == 0 or n%4 == 1:
    for i in range(r):
        print("".join(map(str, board[i])))

elif n != 0 and n%2 == 0:
    for i in range(r):
        print("O"*c)

elif n%4 == 3:
    bomb = [["O"] * c for _ in range(r)]
    for y in range(r):
        for x in range(c):
            if board[y][x] == "O":
                bomb[y][x] = "."
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<c and 0<=ny<r:
                        bomb[ny][nx] = "."
    for i in range(r):
        print("".join(map(str,bomb[i])))

나의 코드 및 설명 03 (맞았습니다)

• 질문게시판에 올라온 반례들을 통해 왜 틀렸는지 이유를 알 수 있었다.
• 나는 3가지 케이스로 나누어 문제를 풀었었다. 그리고 이것이 잘못된 생각이었다는 것을 알 수 있었다.
  1. 시간이 2의 배수일 경우 : 격자판에 꽉찬 폭탄들 출력
  2. 시간이 0(초기 상태)이거나 시간%4 = 1일 경우 : 초기 격자판과 동일하게 출력
  3. 시간%4 = 3일 경우 : 초기 격자판에 놓인 폭탄들이 터진 상태의 격자판 출력
  시간이 증가하게 되어도, 이 세 가지 경우가 반복적으로 진행되는 줄 알았다. 하지만 그게 아니었다.
• 시간이 0(초기 상태)일 때와, 시간%4 =1 일 경우는 서로 격자판이 다를 수 있다.
  아래 그림의 2번째 케이스가 바로 그 예시이다. 따라서 문제를 풀 때, 시간%4 = 3의 경우에는 초기 격자판에 놓여진 폭탄이 터졌을 때의 격자판(bomb1)을 출력하면 되고, 시간%4 = 1의 경우에는 시간%4 = 3의 격자판에 놓여진 폭탄이 터졌을 때의 격자판(bomb2)을 출력하면 된다.

import sys

r,c,n = map(int, input().split())
board = []
for _ in range(r):
    board.append(list(input()))

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

if n <= 1:
    for i in range(r):
        print("".join(map(str, board[i])))

elif n != 0 and n%2 == 0:
    for i in range(r):
        print("O"*c)

else: 
    bomb1 = [["O"] * c for _ in range(r)]
    for y in range(r):
        for x in range(c):
            if board[y][x] == "O":
                bomb1[y][x] = "."
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<c and 0<=ny<r:
                        bomb1[ny][nx] = "."
    bomb2 = [["O"] * c for _ in range(r)]
    for y in range(r):
        for x in range(c):
            if bomb1[y][x] == "O":
                bomb2[y][x] = "."
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0<=nx<c and 0<=ny<r:
                        bomb2[ny][nx] = "."           
    if n%4 == 3:
        for i in range(r):
            print("".join(map(str, bomb1[i])))
    elif n%4 == 1:
        for i in range(r):
            print("".join(map(str, bomb2[i])))

피드백

자기 전에 풀고 자야지 하고 풀었다가 안풀려서 결국 다음 날 푼 문제이다.. 대략 3시간 걸려서 푼 것 같다. 한 시간 안으로 간단하게 풀릴 줄 알았는데 시간초과가 발목을 잡았고, 문제를 잘못 이해하는 바람에 여러 번 시도 끝에 정답 판정을 받을 수 있었다. 소스코드가 복잡해지면, 결과 값을 저장할 임시 테이블을 만드는 것도 괜찮은 방법이다는 것을 깨달았다. 또, 문제를 제대로 읽어야겠다. 구현 문제를 많이 풀어봐야 겠다고 느낀 문제였다.