[DFS/BFS] 16918번, 2468번

1. 봄버맨

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

코드

#봄버맨 22-02-04
import sys
input = sys.stdin.readline
dx=[-1,1,0,0]
dy=[0,0,-1,1]


r,c,n = map(int,input().split())
bomb = [list(input().rstrip()) for _ in range(r)]#그래프 입력받기
#1초면 바로 출력
if n==1:
    for b in bomb:
        print(''.join(b))
#짝수 초 -> 모두 0인 칸으로
elif n%2==0:
    answer = [['O'] * c for _ in range(r)]
    for a in answer:
        print(''.join(a))

#홀수 초 -> 터뜨리고 나머지 0으로 바꾸기
else:
    tmp1 = [['O'] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if bomb[i][j]=='O': tmp1[i][j]='.'
            else:
                for k in range(4):
                    nx=i+dx[k]
                    ny=j+dy[k]
                    if 0<=nx<r and 0<=ny<c:
                        if bomb[nx][ny]=='O':
                            tmp1[i][j]='.'
                            break

    tmp2 = [['O'] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if tmp1[i][j]=='O': tmp2[i][j]='.'
            else:
                for k in range(4):
                    nx=i+dx[k]
                    ny=j+dy[k]
                    if 0<=nx<r and 0<=ny<c:
                        if tmp1[nx][ny]=='O':
                            tmp2[i][j]='.'
                            break
    if n%4==3:
        for t in tmp1:
            print(''.join(t))
    if n%4==1:
        for t in tmp2:
            print(''.join(t))

풀이 방법

1초 단위로 수행을 해도 되지만 시간초과가 날 것 같았다.

그래서 먼저 규칙성을 찾아 경우의 수를 나누었다.
1. 1초일 때 : 그대로 출력
2. 짝수 초일 때: 모두 0으로 바꾸고 출력
3. 4n+3초일 때: 짝수 상태에서 폭탄 터뜨리고 출력 (기준 :입력 그래프)
4. 4n+1초일 때: 짝수 상태에서 폭탄 터뜨리고 출력 (기준 : 3번 그래프)

4번은 한마디로 한 번 더 터뜨린다는 뜻이다.

처음 봄버맨 예제에서 1초일 때와 5초일 때의 그래프 모양이 같아서 1번과 4번의 경우를 모두 그대로 출력하는 것으로 했었는데,반례를 찾아보니 4가지로 경우의 수를 나눠야 한다는 것을 알았다.

참조한 반례 링크 - https://www.acmicpc.net/board/view/34611

2. 안전영역

링크 - https://www.acmicpc.net/problem/2468

#안전영역 22-02-04
import sys
from collections import deque
input = sys.stdin.readline
dx=[-1,1,0,0]
dy=[0,0,-1,1]

def bfs(i,j,h):
    q = deque()
    q.append((i,j))
    visited[i][j]=True
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            if 0<=nx<n and 0<=ny<n:
                if graph[nx][ny]>h and not visited[nx][ny]:
                    q.append((nx,ny))
                    visited[nx][ny]=True


n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)] #입력받기

max_rain=0
for i in range(n):
    max_rain = max(max_rain,max(graph[i]))

answer=0
for i in range(0,max_rain+1):
    count=0
    visited=[[False]*n for _ in range(n)]
    #개수 세기
    for x in range(n):
        for y in range(n):
            if graph[x][y]>i and not visited[x][y]:
                bfs(x,y,i)
                count+=1
    answer=max(count,answer)

print(answer)

풀이 방법

bfs로 탐색을 하면 되는 기본적인 문제 유형들 중 하나였다.
높이를 0부터 max값까지 탐색을 해야돼서 시간초과가 날까 걱정했는데 나지 않았다.

1. 입력받은 그래프에서 가장 깊은 높이를 찾는다 (max_rain)
2. 높이 0부터 max_rain까지 탐색을 하면서 안전영역의 개수를 구한다.
   2-1. 그래프 순차 탐색을 하며 높이가 i보다 높다면 BFS탐색을 한다.
   2-2. bfs를 완료할 때 마다 count를 1씩 증가시킨다.
3. answer와 count를 비교하여 최댓값을 저장하도록 한다.

.
.
.

개인적으로 같은 실버1인데 봄버맨이 훨씬 어려웠다..