난 나뭇잎 마을의 초대 호카게인 센쥬 하시라마의 동생, 센쥬 토비라마라고 한다. 지금 우리 마을은 크나큰 위기에 빠져있다. 우리와 끊이지 않는 악연을 지닌 우치하 가문의 수장 우치하 마다라가 구미를 끌고 마을을 습격했기 때문이지. 형은 호카게로서 마다라와 전투를 벌이고 있고 마을 주민들에게 피해가 갈까 봐 제대로 전투하지 못하고 있어. 지금 놈의 화둔이 마을로 넘어오지 못하게 우리 형의 목둔이 막아주고 있으니 나무가 크게 불타기 전에 미리 주민들을 대피시켜야 해. 나뭇잎 마을을 지키려면 네 도움이 필요해. 

현재 상황은 마을 뒷산에서 전투가 일어나고 있고, 형의 나무가 불길을 막아서고 있어. 지도를 통해 살펴보면 마을 뒷산은 N × M 의 직사각형의 격자에 해당하는 형태임을 알 수 있지. 아, 지도의 밖은 돌로 둘러싸여 있어 불이 퍼질 수 없으니 걱정하지 마.

불은 상하좌우로 인접한 나무를 통해서만 퍼져나갈 수 있고, 어떤 날에서 그다음 날로 넘어갈 때, 각 불은 동시에 퍼지게 돼. 불과 접촉한 나무는 다음 날 전부 불에 타서 불길이 되어버려. 하지만, 돌이 있는 지역은 불이 붙지 않아. 

너도 알다시피 대피에는 시간이 굉장히 중요해. 우리는 주민들이 안전히 대피할 수 있도록 만날 수 있는 모든 불이 합쳐지는 최소 시간과 그때의 불의 크기를 구해야만 해. 불이 돌에 막혀 모든 불이 하나로 합쳐지지 않을 수도 있는데, 그럴 땐 합쳐질 수 있는 모든 불이 합쳐지는 최소 시간과 그때의 불의 크기의 합을 구하면 돼.

불이 합쳐진다는 것은 불이 다른 불과 상하좌우로 인접하게 되는 것을 뜻하고, 불의 크기는 불이 붙은 칸의 개수를 말해.

부탁해! 어서! 문제를 해결해서 우리 마을과 형에게 도움을 줘!

입력

첫 번째 줄에 지도의 크기를 나타내는 정수 이 주어진다. (1 ≤ N, M ≤ 2,000)

두 번째 줄부터 번째 줄까지 로 이루어진 첫날 지도가 표시된다. (불 = , 나무 = , 돌 = )

출력

만날 수 있는 모든 불이 만나는 최소 시간과 그때의 불의 크기의 합을 출력한다. 첫날은 일차이다. 즉, 처음부터 합칠 수 있는 모든 불이 합쳐져 있다면 최소 시간은 이다.

만약 퍼질 불이 없다면, "0 0"을 출력한다.

풀이 과정

2022년 9월에 도전했다가 실패하고 1년 반(...) 뒤에 재도전했다.

 

다음 과정을 거쳐 구현했다.

1. 불 영역을 BFS 하면서, 그룹 번호 부여하기 

2. 돌로 나누어진 영역을 BFS 하면서, 돌로 나누어진 영역 중 불이 존재하는 영역 카운트하기

3. 불이 주변 나무로 퍼지는 BFS 를 진행하면서, 다른 불과 인접하면 유니온 파인드로 그룹 개수 줄이기 -> 불 영역 전체 개수가 돌로 나누어진 영역 중 불이 존재하는 영역 개수가 된다면 BFS 를 종료하고 최소 시간과 불의 크기 합 출력하기

 

1. 불 영역 그룹화 

row = [-1, 1, 0, 0]
col = [0, 0, -1, 1]

group = [[-1 for _ in range(m)] for _ in range(n)]

group_cnt = 1
last_size = 0
for i in range(n):
    for j in range(m):
        if maps[i][j] == '0' and group[i][j] == -1:
            queue = deque()
            queue.append([i, j])
            group[i][j] = group_cnt
            size = 0

            while queue:
                now = queue.popleft()
                size += 1
                for d in range(4):
                    ny = now[0] + row[d]
                    nx = now[1] + col[d]

                    if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == '0' and group[ny][nx] == -1:
                        queue.append([ny, nx])
                        group[ny][nx] = group_cnt

            group_cnt += 1
            last_size = size

N x M 영역을 탐색하여, 그룹 번호가 아직 붙지 않은 ( -1 인 ) 불 영역이 있다면 BFS 탐색을 진행했다.

group_cnt 변수에 해당 그룹이 몇 번 그룹인지 기록하도록 하고, 불 영역의 전체 개수를 카운트했다.

 

last_size 변수를 사용했는데, 불 영역이 1개일 경우 이미 다 합쳐진 상태이므로 해당 영역의 크기를 출력할 때 불 영역의 크기를 바로 출력할 수 있도록 하기 위해 사용했다.

 

if group_cnt == 1: print(0, 0)
elif group_cnt == 2: print(0, last_size)

 

불 영역이 1개일 경우 group_cnt 가 2이다. group_cnt 가 2일때 0, (불 영역 크기) 를 출력한다.

group_cnt 가 1에서 전혀 증가하지 않았다면 불 자체가 없으므로 0, 0을 출력한다.

 

예제 1번의 경우 다음과 같이 그룹화된다.

# Input
00111110100
01111110111
01111111110
11110011111
11000000111

# Output
11000002033
10000002000
10000000004
00005500000
00555555000

 

2. 돌로 나누어진 영역 카운트

돌로 나누어져 모든 불이 합쳐지지 않는 경우를 고려하기 위해 돌로 나누어진 영역을 카운트했다.

N x M 영역이 돌로 인해 나누어져 있다면, 돌로 나누어진 영역마다 불이 다 퍼지면 되겠다고 생각할 수도 있겠지만,

01111 // 영역이 2개로 나누어져 있고 불 영역은 3개. 
22222 // 전부 합쳐지면 불 영역은 2개가 됨.
01110

01111 // 영역이 2개로 나누어져 있지만 불 영역은 1개 뿐, (0, 1)
22222
11111

01211 // 영역이 4개로 나누어져 있지만 불 영역은 3개 뿐. (0, 3)
22222
01210

 

위와 같이 돌로 나누어져 있어도 해당 영역에 불이 없는 경우도 생각해야 하므로, 돌로 나누어진 영역 중 불이 존재하는 영역의 개수를 세야 한다. 

 

goal = 0
visited_stone = [[0 for _ in range(m)] for _ in range(n)]

queue_fire = deque()

for i in range(n):
    for j in range(m):
        if maps[i][j] == '0': queue_fire.append([i, j])
        if maps[i][j] != '2' and visited_stone[i][j] == 0:
            queue = deque()
            queue.append([i, j])
            visited_stone[i][j] = 1
            available = 0

            while queue:
                now = queue.popleft()
                if maps[now[0]][now[1]] == '0': available = 1
                for d in range(4):
                    ny = now[0] + row[d]
                    nx = now[1] + col[d]

                    if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] != '2' and visited_stone[ny][nx] == 0:
                        queue.append([ny, nx])
                        visited_stone[ny][nx] = 1

            if available == 1:
                goal += 1

queue_fire 은 이후에 불 BFS 를 진행할 때를 위해 불 정보를 미리 저장하기 위해 사용했다.

 

평범한 BFS 를 진행하되, 돌로 나누어진 영역 안에 불 타일이 있다면 goal 변수를 1씩 카운트했다.

 

이전에 group_cnt 변수로 전체 불 영역 개수를 카운트 ( group_cnt - 1 개 ) 했으므로, 마지막 목표는 불 영역들이 합쳐지면서 전체 불 영역 개수가 돌로 나누어진 영역 중 불이 존재하는 영역 개수가 될 때까지 불 전파를 진행해야 한다.

( 각각 돌 영역 안에서 불이 전부 합쳐지면 영역 당 한 개의 불 영역이 차지해야 한다. 만약 전체 불 영역 개수가 6개이고 돌로 나누어진 영역 중 불이 존재하는 영역 개수가 5개이면 어느 한 영역이 아직 한 개의 불 영역으로 합쳐지지 않았음을 알 수 있다. )

 

3. 불 전파 BFS

time = 0
while queue_fire:
    if goal >= group_cnt - 1:
        break
    queue_size = len(queue_fire)
    for s in range(queue_size):
        now = queue_fire.popleft()

        for d in range(4):
            ny = now[0] + row[d]
            nx = now[1] + col[d]

            if 0 <= ny < n and 0 <= nx < m:
                if maps[ny][nx] == '1':
                    queue_fire.append([ny, nx])
                    group[ny][nx] = group[now[0]][now[1]]
                    maps[ny][nx] = '0'
                    for dd in range(4):
                        nny = ny + row[dd]
                        nnx = nx + col[dd]

                        if 0 <= nny < n and 0 <= nnx < m and maps[nny][nnx] == '0' and group[nny][nnx] != group[ny][nx]:
                            res = union(nny, nnx, ny, nx)
                            if res == -1: continue
                            group[nny][nnx] = res
                            group[ny][nx] = res
    time += 1

불을 BFS 를 통해 전파시킨다. 

불을 인접한 4방향으로 전파했을 때, 그 전파한 곳에서 한번 더 주변 탐색을 진행한 뒤 다른 그룹의 불이 존재한다면 (즉 불을 전파했을 때 인접한 다른 그룹의 불이 존재한다면) union 을 진행하여 영역 개수를 줄였다.

 

arr = [i for i in range(group_cnt)]
def parent(a):
    if a == arr[a]: return a
    arr[a] = parent(arr[a])
    return arr[a]

def union(ay, ax, by, bx):
    global group_cnt
    group[ay][ax] = parent(group[ay][ax])
    group[by][bx] = parent(group[by][bx])
    a = group[ay][ax] 
    b = group[by][bx]

    if a != b:
        group_cnt -= 1
        if a < b:
            arr[group[by][bx]] = a
            return a
        else:
            arr[group[ay][ax]] = b
            return b
    return -1

유니온 파인드를 사용함으로써 여러 개의 불이 합쳐질 때 중복으로 영역이 합쳐지는 경우가 없도록 고려한다. (이미 부모는 합쳐졌는데 전파가 아직 안 된 영역에서 합쳐질 경우 등)

 

다음과 같이 불 전파 BFS 를 진행하면서, 불 영역 전체 개수가 돌로 나누어진 영역 중 불이 존재하는 영역 개수가 된다면 BFS 를 종료하고 걸린 시간과 전체 불 크기 합을 출력한다.

 

전체 코드

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

n, m = map(int, input().rstrip().split())
maps = [list(input().rstrip()) for _ in range(n)]

# 1. 불 영역을 세서 그룹화
# 2. 돌로 나눠진 영역 세기 ( 불이 존재하는 돌 영역 개수가 최종 불 합쳐져야 하는 목표 )
# 3. 불 BFS 를 하되 다른 불과 붙을 때 union을 하면서 영역 줄이기

row = [-1, 1, 0, 0]
col = [0, 0, -1, 1]

group = [[-1 for _ in range(m)] for _ in range(n)]

group_cnt = 1
last_size = 0
for i in range(n):
    for j in range(m):
        if maps[i][j] == '0' and group[i][j] == -1:
            queue = deque()
            queue.append([i, j])
            group[i][j] = group_cnt
            size = 0

            while queue:
                now = queue.popleft()
                size += 1
                for d in range(4):
                    ny = now[0] + row[d]
                    nx = now[1] + col[d]

                    if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == '0' and group[ny][nx] == -1:
                        queue.append([ny, nx])
                        group[ny][nx] = group_cnt

            group_cnt += 1
            last_size = size

if group_cnt == 1: print(0, 0)
elif group_cnt == 2: print(0, last_size)
else:
    goal = 0
    visited_stone = [[0 for _ in range(m)] for _ in range(n)]

    queue_fire = deque()

    for i in range(n):
        for j in range(m):
            if maps[i][j] == '0': queue_fire.append([i, j])
            if maps[i][j] != '2' and visited_stone[i][j] == 0:
                queue = deque()
                queue.append([i, j])
                visited_stone[i][j] = 1
                available = 0

                while queue:
                    now = queue.popleft()
                    if maps[now[0]][now[1]] == '0': available = 1
                    for d in range(4):
                        ny = now[0] + row[d]
                        nx = now[1] + col[d]

                        if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] != '2' and visited_stone[ny][nx] == 0:
                            queue.append([ny, nx])
                            visited_stone[ny][nx] = 1
                
                if available == 1:
                    goal += 1
    
    # 목표 불 그룹 개수 / 현재 불 그룹 개수
    # print(goal, group_cnt - 1)

    arr = [i for i in range(group_cnt)]
    def parent(a):
        if a == arr[a]: return a
        arr[a] = parent(arr[a])
        return arr[a]

    def union(ay, ax, by, bx):
        global group_cnt
        group[ay][ax] = parent(group[ay][ax])
        group[by][bx] = parent(group[by][bx])
        a = group[ay][ax] 
        b = group[by][bx]
        
        if a != b:
            group_cnt -= 1
            if a < b:
                arr[group[by][bx]] = a
                return a
            else:
                arr[group[ay][ax]] = b
                return b
        return -1

    time = 0
    while queue_fire:
        if goal >= group_cnt - 1:
            break
        queue_size = len(queue_fire)
        for s in range(queue_size):
            now = queue_fire.popleft()

            for d in range(4):
                ny = now[0] + row[d]
                nx = now[1] + col[d]

                if 0 <= ny < n and 0 <= nx < m:
                    if maps[ny][nx] == '1':
                        queue_fire.append([ny, nx])
                        group[ny][nx] = group[now[0]][now[1]]
                        maps[ny][nx] = '0'
                        for dd in range(4):
                            nny = ny + row[dd]
                            nnx = nx + col[dd]

                            if 0 <= nny < n and 0 <= nnx < m and maps[nny][nnx] == '0' and group[nny][nnx] != group[ny][nx]:
                                res = union(nny, nnx, ny, nx)
                                if res == -1: continue
                                group[nny][nnx] = res
                                group[ny][nx] = res
        time += 1

    sums = 0
    for i in range(n): sums += maps[i].count('0')
    print(time, sums)
저작자표시 비영리 변경금지

'-- 예전 기록 > BOJ' 카테고리의 다른 글

[ BOJ ] 2961 : 도영이가 만든 맛있는 음식 ( SILVER 2 ) / Python  (0) 2024.02.07
[ BOJ ] 13414 : 수강신청 ( SILVER 3 ) / Python  (0) 2024.02.07
[ BOJ ] 20922 : 겹치는 건 싫어 ( SILVER 1 ) / Python  (0) 2024.02.06
[ BOJ ] 5567 : 결혼식 ( SILVER 2 ) / Python  (0) 2024.02.06
[ BOJ ] 18917 : 수열과 쿼리 38 ( SILVER 3 ) / Python  (0) 2024.02.06

티스토리툴바