백준_16918_봄버맨 (python)

★ 접근

 r,c,n의 크기가 최대 200이기 때문에 bfs로 풀까 생각했지만 폭탄이 동시에 깔리고 동시에 터지는 문제는 bfs로는 풀기 힘든 상황들이 자주 발생해서 쌩 구현을 해도 된다고 생각하고 접근  

★ 풀이

n이 1초 => 초기 상태 출력

n이 짝수 => 모든 칸이 폭탄

그 외 = > 0초 폭탄, 1초 폭탄, 2초 폭탄을 나누어서

2초를 터트리고 0초를 1초로 만들고 => 다음 1초동안 모든칸 포탄 채우고 1초 => 2초 폭탄 0초 폭탄 생성
위 구문을 n-2초 동안 반복

★ 코드

import sys
input = sys.stdin.readline
r,c,n, = map(int,input().split())
graph = [list(input().rstrip()) for _ in range(r)]
isgraph = set([(i,j) for i in range(r) for j in range(c)])
if n == 1:
    for lis in graph:
        print(''.join(lis))
else:
    if n % 2 == 0:
        for i in range(r):
            print('O'*c)
    else:
        zero = set()
        one = set()
        two = set()
        temp = set()
        dx = [-1,1,0,0]
        dy = [0,0,-1,1]    
        for i in range(r):
            for j in range(c):
                if graph[i][j] == '.':
                    zero.add((i,j))
                else:
                    two.add((i,j))    
        for i in range(n-2): # n이 2초면 아에 이 반복에 안 들어갈 것이고 n이 3초면 한 번 반복 ok
            if i % 2 == 0:
                temp = set()
                for x,y in two:
                    temp.add((x,y))
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if 0 <= nx < r and 0 <= ny < c:
                            temp.add((nx,ny))
                zero = zero - temp # 이러면 zero에 있던 폭탄들중에서도 해당되는 것들은 터졌다.
                one = zero # 이제 0초가 1초가 된다..
            else:
                two = one
                zero = isgraph - one # 전체에서 2초를 뺀것이 이제 0초가 된다.
        for i in range(r):
            for j in range(c):
                if (i,j) in one:
                    print("O", end='')
                else:
                    print(".", end='')
            print()

 

★ 회고

 폭탄이 터지고 생기고를 반복하면서 격자 폭탄이 생기는 모양이 계속 바뀐다고 생각을 했다. 그래서 시뮬레이션 기법처럼 풀었다. 다 풀고 시간이 오래 걸리길래 문제를 다시 읽어보면서 힌트를 발견했고 힌트에서 격자의 모양이 반복되는 것을 알 수 있었다. 쉬운 문제들은 힌트를 잘 안 보고 푸는 풀어보자는 마인드였는데  쉬운 문제여도 힌트를 잘 봐야겠다.