[BOJ] 16918 봄버맨(풀이 방식 2종류)

내 최초 풀이

# step 1 봄버맨 폭탄 설치 설치시간 동일
# step 2 정지
# step 3 폭탄이 설치되어 있지않은 모든칸에 폭탄을 설치
# step 4 1초가 지난후 3초전에 설치된 폭탄이 모두 폭발한다.
# step 5 step 3 ~ step 4 반복
dx = [1,-1,0,0]
dy = [0,0,1,-1]

R,C,N = map(int,input().split())
# R은 행 C은 열 N은 초
bomb = [list(input()) for _ in range(R)]
times = [[-1]*C for _ in range(R)]

for x in range(R):
    for y in range(C):
        if bomb[x][y] == 'O':
            times[x][y] = 3

        

for k in range(N):
    bomb_set = set()
    if k%2:
        for x in range(R):
            for y in range(C):
                times[x][y] -= 1
                if bomb[x][y] == '.':
                    times[x][y] = 3
                    bomb[x][y] = 'O'
    else:
        for x in range(R):
            for y in range(C):
                times[x][y] -= 1
                if times[x][y] == 0:
                    bomb_set.add((x,y))
                    for i in range(4):
                        nx = x + dx[i]
                        ny = y + dy[i]
                        if 0<=nx<R and 0<=ny<C:
                            bomb_set.add((nx,ny))
    for nx,ny in bomb_set:
        bomb[nx][ny] = '.'





for rows in range(R):
    print(''.join(bomb[rows]))

내 최초 풀이 방식은 문제의 방식을 그대로 따라한것이다.

문제를 보면 알수 있듯이 2의 배수의 시간일때는 폭탄을 설치해주는 것을 알 수 있다.

폭탄을 저장할 수 있는 리스트와 폭탄이 폭파되기까지 걸리는 시간을 저장해주기 위한 리스트를 두 종류를 준비해주었다.

그래서 2의 배수의 시간일때에는 폭탄을 설치해주고, 그 외의 시간에는 폭탄의 시간이 줄어들면서 터지는 폭탄의 위치들을 집합에 모아주고, 그것을 폭파해주는 방식으로 해주어 시뮬레이션을 해주었다.

 

이 풀이는 단순히 문제에 적혀져 있는 방식대로 시뮬레이션을 돌린거다 보니, 시간이 오래걸렸다.

 

 

# heecheol1508 클론코딩


R,C,N = map(int,input().split())
board = [list(input()) for _ in range(R)]

if N%2 == 0:
    # 시간이 짝수일때는 무조건 전부 폭탄이 설치되기 때문에, 시간이 짝수일때는 전부 폭탄이 설치된 경우를 출력하면 된다.
    for _ in range(R):
        print('O'*C)
elif N == 1:
    # 1초일때는 초기 상태를 그대로 출력하면 된다.
    for row in board:
        print(''.join(row))
else:
    # 그 외의 시간일때는 나머지를 출력하면 된다.
    # 그런데 해당문제에서는 폭탄이 터지는 경우는 크게 2가지 밖에 없다.
    # 최초 설치된 폭탄 즉 0초에 설치된 폭탄이 터지는 경우와 
    # 2초에 설치된 폭탄 중에 최초 설치된 폭탄과 인접하지 않는 폭탄이 터지는 경우 2가지밖에 없다.
    # 그렇기 때문에 최초 설치된 폭탄이 터ㅣ는 시간대와 2초에 설치된 폭탄이 터지는 경우 두가지만 구분하면 된다.
    # 최초 설치된 폭탄이 터지는 시간대는 3초,7초,11초,15초로 4초 간격으로 터진다. 
    # 2초에 설치된 폭탄 중 최초 설치된 폭탄과 인접하지 않은 폭탄이 터지는 시간은 5초,9초,13초,17초이다.
    # 먼저 터지는 것은 최초 설치된 폭탄의 위치와 그와 인접한 폭탄이다. 그 부분만 폭탄이 터지는걸로 해주고 나머지는 폭탄이 설치된 걸로 만들어주면 된다.
    # 그래서 최초 폭탄이 터졌을때의 상황을 만들어주고, 그때의 시간이 3,7,11,15일때에는 그대로 출력하고,
    # 그때가 아닐때에는 2초에 설치된 폭탄이 터지는 경우이니 한번 더 폭탄이 터지는 것을 반복해주면 된다.
    bomb = []
    for x in range(R):
        for y in range(C):
            if board[x][y] == 'O':
                board[x][y] = '.'
                bomb.append((x,y))
            else:
                board[x][y] = 'O'
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    for bx,by in bomb:
        for i in range(4):
            nx = bx + dx[i]
            ny = by + dy[i]
            if 0<=nx<R and 0<=ny<C:
                board[nx][ny] = '.'

    times = (N-3)%4
    if not times:
        for row in board:
            print(''.join(row))
    else:
        bomb = []
        for x in range(R):
            for y in range(C):
                if board[x][y] == 'O':
                    bomb.append((x,y))
                    board[x][y] = '.'
                else:
                    board[x][y] = 'O'
        for bx,by in bomb:
            for i in range(4):
                nx = bx + dx[i]
                ny = by + dy[i]
                if 0<=nx<R and 0<=ny<C:
                    board[nx][ny] = '.'
        for row in board:
            print(''.join(row))

위의 코드 같은 경우 백준의 heecheol1508님의 코드를 분석하고, 이해한뒤 클론코딩한 것이다.

문제를 보면 2의 배수시간일때에는 폭탄이 빈곳에 설치하기 때문에 모든 배열에 폭탄이 설치되는 것이 알 수 있다.

그래서 주어진 시간이 2의 배수이면 폭탄이 전부 설치된 것을 보여주면 된다.

그리고 폭탄이 터지는 경우는 2가지 케이스이다.

최초로 설치된 폭탄이 터지는 경우와 2초에 설치한 폭탄이 터지는 경우이다.

최초의 설치된 폭탄과 2초에 설치된 폭탄이 터질때 서로 영향을 못준다. 왜냐하면, 폭탄이 터지면서 상하좌우를 터트리고 연쇄 폭파가 일어나지 않기 때문에, 일종의 안전지대가 생성이 되는 것이다. 

그렇기 때문에 이런한 성향을 이용하여, 계산하면 된다.

최초 설치된 폭탄은 3초에 최초로 터지고 그 뒤로 7초 11초 15초 4의 간격으로 터진다.

그래서 처음에 설치된 폭탄들이 터졌을때의 상황을 만들어주고,

위의 시간이 아니면 2초에 설치된 폭탄들이 터지는 것을 구현해주면 된다.