[BOJ/python] 14502번 연구소

 

https://www.acmicpc.net/problem/14502

14502번: 연구소

문제 해석

 

이 문제는 바이러스인 2가 상하좌우로 퍼지는데 이를 벽 3개를 생성하여 가장 많은 안전 영역의 크기를 구하는 문제이다.

 

---

코드

from collections import deque
input = __import__('sys').stdin.readline

# Input
n, m = map(int, input().split())

arr = []
makeWall = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

# makeWall: 벽을 생성가능한 공간의 좌표 (0의 좌표) 리스트
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0: makeWall.append((i,j))

setWall = []

# bfs를 위한 방향 좌표
dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def bfs():
    global ansTemp
    while q:
        temp = q.popleft()
        visit[temp[0]][temp[1]] = True
        for d in dir:
            dx, dy = temp[0] + d[0], temp[1] + d[1]
            # arr범위 안에 있고, 방문하지 않았고, 해당 좌표가 공간(0) 인경우 바이러스 감염
            if 0 <= dx < n and 0 <= dy < m and not visit[dx][dy] and arr[dx][dy] == 0:
                # 감염된 구역이므로 -1
                ansTemp -= 1
                visit[dx][dy] = True
                q.append((dx, dy))


ans = 0
# i, j, k를 하나씩 늘려 중복되지 않은 벽을 3개 선택 (완전 탐색)
for i in range(len(makeWall)):
    setWall.append(makeWall[i])
    for j in range(i + 1, len(makeWall)):
        setWall.append(makeWall[j])
        for k in range(j + 1, len(makeWall)):
            setWall.append(makeWall[k])
            # setWall에 생성할 벽의 좌표 3개가 존재

            # 선택된 위치를 벽으로 만듬
            for wall in setWall:
                arr[wall[0]][wall[1]] = 1

            # bfs 준비
            visit = [[False] * m for _ in range(n)]
            q = deque()

            # 안전 영역의 크기는 벽을 3개 생성했으므로 -3 
            ansTemp = len(makeWall) - 3

            # arr 완전탐색을 통해 답 구하기
            for x in range(n):
                for y in range(m):
                    # arr좌표에 바이러스가 존재(2) 할때 퍼지기 시작
                    if arr[x][y] == 2 and not visit[x][y]:
                        q.append((x,y))
                        bfs()
            ans = max(ans, ansTemp)
                        
            
            # 선택된 벽을 다시 0으로 바꾸고
            for wall in setWall:
                arr[wall[0]][wall[1]] = 0
            
            # pop을 통해 다음 벽 선택
            setWall.pop()
        setWall.pop()
    setWall.pop()

print(ans)

---

문제 풀이

 

이 문제에서 주어진 n, m의 크기가 작으므로 0의 영역에 3가지 벽을 세울 수 있는 모든 경우 만들고 해당 영역에서 bfs를 통해 안전 영역의 크기를 구하는 방식으로 구현했다.

 

# makeWall: 벽을 생성가능한 공간의 좌표 (0의 좌표) 리스트
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0: makeWall.append((i,j))

이를 위해 생성 가능한 벽 공간의 위치를 알아야 하므로 0의 좌표를 (x, y) 형태로 저장한 배열을 만들었다.

 

setWall = []

# i, j, k를 하나씩 늘려 중복되지 않은 벽을 3개 선택 (완전 탐색)
for i in range(len(makeWall)):
    setWall.append(makeWall[i])
    for j in range(i + 1, len(makeWall)):
        setWall.append(makeWall[j])
        for k in range(j + 1, len(makeWall)):
            setWall.append(makeWall[k])
            # setWall에 생성할 벽의 좌표 3개가 존재

setWall의 배열을 생성하고 makeWall에서 중복되지 않은 3개의 좌표를 선택하기 위해 다음과 같은 알고리즘을 통해

setWall에 넣어주었다. 

여기서 직접적으로 arr에 벽을 바꾸어 주지 않고 setWall에 저장한 후 벽을 바꾸는 이유는 배열을 다시 초기화 하는 것보다 좌표를 3개 저장하여 이를 바꾸는 것이 더 효율적이라고 생각했다.

 

            # 선택된 위치를 벽으로 만듬
            for wall in setWall:
                arr[wall[0]][wall[1]] = 1

            # bfs 준비
            visit = [[False] * m for _ in range(n)]
            q = deque()

            # 안전 영역의 크기는 벽을 3개 생성했으므로 -3 
            ansTemp = len(makeWall) - 3

            # arr 완전탐색을 통해 답 구하기
            for x in range(n):
                for y in range(m):
                    # arr좌표에 바이러스가 존재(2) 할때 퍼지기 시작
                    if arr[x][y] == 2 and not visit[x][y]:
                        q.append((x,y))
                        bfs()
            ans = max(ans, ansTemp)

이후 선택한 3개의 좌표를 벽으로 만들고 arr을 완전 탐색하는 bfs 통해 안전 영역의 크기를 구했다.

ansTemp는 안전 구역의 크기(0의 개수) - 3(벽을 생성하면서 없어진 안전 구역의 수)로 선언해 주었다.

 

# bfs를 위한 방향 좌표
dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def bfs():
    global ansTemp
    while q:
        temp = q.popleft()
        visit[temp[0]][temp[1]] = True
        for d in dir:
            dx, dy = temp[0] + d[0], temp[1] + d[1]
            # arr범위 안에 있고, 방문하지 않았고, 해당 좌표가 공간(0) 인경우 바이러스 감염
            if 0 <= dx < n and 0 <= dy < m and not visit[dx][dy] and arr[dx][dy] == 0:
                # 감염된 구역이므로 -1
                ansTemp -= 1
                visit[dx][dy] = True
                q.append((dx, dy))

bfs는 다음과 같이 구현했으며, 감염된 구역을 따로 2로 바꿀 필요가 없다.

이는 어차피 감염된 구역은 방문했기 때문에 이후 재감염이 되어 중복으로 셈되는 경우가 없다.

따라서 감염되는 조건은 dx, dy가 arr에 존재하고, 방문하지않고, 0일경우 모두 만족해야 감염되도록 하였다.

이후 감염 되었으므로 안전 영역의 크기를 1씩 빼주었다.

 

            # 선택된 벽을 다시 0으로 바꾸고
            for wall in setWall:
                arr[wall[0]][wall[1]] = 0
            
            # pop을 통해 다음 벽 선택
            setWall.pop()
        setWall.pop()
    setWall.pop()

이후 아까 선택하여 바뀌었던 벽(1)들을 다시 공간(0)으로 바꾸어 주고,

다음 벽을 선택하기위해 pop을 해주었다.

 

이후 max를 통해 가장 큰 값이 출력된다.

 

원문: https://ddingmin00.tistory.com/30

[BOJ/python] 14502번 연구소