백준 #31863 내진 설계

문제 링크

[31863 내진 설계]

문제 설명

진원지에서 지진이 발생하고 지진이 전파되면서 무너지는 건물의 개수와 무너지지않는 건물의 개수를 체크하는 문제

코드

import sys
input = sys.stdin.readline
from collections import deque

def bfs(i, j):
    q = deque()
    visited[i][j] = 1
    # 처음 2칸 지진 따로 구현
    for k in range(4):
        for l in range(1, 3):
            ni, nj = i + l * dr[k], j + l * dc[k]
            if ni < 0 or ni >= N or nj < 0 or nj >= M:
                break
            if arr[ni][nj] == "|":
                break
            if arr[ni][nj] == "*":
                visited[ni][nj] = 1
                q.append((ni, nj))
            if arr[ni][nj] == "#":
                visited[ni][nj] = 1
    while q:
        r, c = q.popleft()
        for k in range(4):
            nr, nc = r + dr[k], c + dc[k]
            if nr < 0 or nr >= N or nc < 0 or nc >= M:
                continue
            if arr[nr][nc] == "|" or arr[nr][nc] == ".":
                continue
            if arr[nr][nc] == "*":
                if visited[nr][nc] == 0:
                    visited[nr][nc] = 1
                    q.append((nr, nc))
            elif arr[nr][nc] == "#":
                if visited[nr][nc] == 0:
                    visited[nr][nc] = 1
                elif visited[nr][nc] == 1:
                    visited[nr][nc] = 2
                    q.append((nr, nc))

N, M = map(int, input().split())
arr = [list(input().rstrip()) for _ in range(N)]
visited = [[0] * M for _ in range(N)]
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for i in range(N):
    for j in range(M):
        if arr[i][j] == "@":
            bfs(i, j)

broken = 0
not_broken = 0
for i in range(N):
    for j in range(M):
        if arr[i][j] == "*":
            if visited[i][j] == 0:
                not_broken += 1
            else:
                broken += 1
        elif arr[i][j] == "#":
            if visited[i][j] <= 1:
                not_broken += 1
            else:
                broken += 1

print(broken, not_broken)

풀이

딱 보자마자 BFS로 풀어야 겠다고 생각이 들었다. 진원지에서 전파되는 지진은 두칸이 전파되기 때문에 따로 구현을 해주었다. 3번정도 틀렸었는데 틀린 원인은 진원지를 따로 구현해주었으면 큐에 넣어주지 않아야하는데 처음에 큐에 넣고 시작을해서 중복으로 전파가 이루어져서 틀렸던것…

오늘 날씨도 별로고 기분도 별로여서 그런지 문제풀면서 좀 짜증이 났었다..