[BOJ/python] 14502번 연구소

2022. 5. 13. 06:33· Koala - 6기/코딩테스트 준비 스터디

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

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

문제 해석

 

이 문제는 바이러스인 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번 연구소

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서

ddingmin00.tistory.com

 

 

 

 

 

 

 

저작자표시 (새창열림)

'Koala - 6기 > 코딩테스트 준비 스터디' 카테고리의 다른 글

[백준/C++] 1916번 최소비용 구하기  (0) 2022.05.16
[백준 / python] 17390번: 이건 꼭 풀어야 해!  (0) 2022.05.15
[백준/C++] 14267번 회사 문화 1  (0) 2022.05.13
[BOJ / Python] 1874 - 스택 수열  (0) 2022.05.09
[BOJ/python] 11286번 절댓값 힙  (0) 2022.05.09
'Koala - 6기/코딩테스트 준비 스터디' 카테고리의 다른 글
  • [백준/C++] 1916번 최소비용 구하기
  • [백준 / python] 17390번: 이건 꼭 풀어야 해!
  • [백준/C++] 14267번 회사 문화 1
  • [BOJ / Python] 1874 - 스택 수열
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1884)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • BOJ
  • C++
  • 파이썬
  • dfs
  • 백트래킹
  • BFS
  • 백준
  • dp

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[BOJ/python] 14502번 연구소
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.