이 영역을 누르면 첫 페이지로 이동
포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

페이지 맨 위로 올라가기

포렌식 & 개발 이야기 - Forensics & Development

Pental - Forensics / iOS / Windows / Android / Kakaotalk / Telegram / Etc

백준 14502 - 연구소 (파이썬)

  • 2025.02.26 22:32
  • Programming/백준
글 작성자: pental

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

풀이

이 문제는 BFS와 완전 탐색을 조합하여 해결하는 문제이다.

문제에서는 연구소에서 벽을 3개 세우는 모든 경우의 수를 고려하고, 이후 바이러스가 퍼지는 과정을 BFS로 시뮬레이션하여 안전 영역의 최대 크기를 구하는 방식으로 해결한다.

사용한 해결 전략은 다음과 같다.

  1. 연구소에서 빈칸 (0)의 좌표를 찾는다.
  2. 빈칸 중 3곳을 선택하여 벽을 세운다. (여기서 필자는 combinations()를 통해 조합을 구함)
  3. BFS를 이용해서 바이러스를 퍼뜨린다.
  4. 바이러스가 퍼진 후 남은 안전 영역(0)을 계산한다.
  5. 벽을 세우기 전 상태로 되돌린다. (백트래킹)
  6. 가장 큰 안전 영역 값을 저장하여 출력한다.
cells = [(i, j) for i in range(N) for j in range(M) if B[i][j] == 0]

일단 연구소의 모든 빈 칸 위치를 리스트로 저장한다.

for combination in combinations(cells, 3):

combinations(celss, 3) 을 이용해 빈 칸 중 3개를 선택하는 모든 경우를 탐색한다.

for row, col in combination:
    B[row][col] = 1  # 벽 세우기

선택한 3개의 위치에 벽을 세운다.

visit = [[False] * M for _ in range(N)]
queue = deque()

for i in range(N):
    for j in range(M):
        if B[i][j] == 2:
            queue.append((i, j))
            visit[i][j] = True

queue에 초기 바이러스 위치를 넣고 BFS를 준비한다.

while queue:
    r, c = queue.popleft()

    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]

        if 0 <= nr < N and 0 <= nc < M and not visit[nr][nc] and B[nr][nc] == 0:
            queue.append((nr, nc))
            visit[nr][nc] = True

상하좌우 방향으로 바이러스를 확산하고, visit[nr][nc] = True 를 통해 방문 처리를 진행한다.

safe = 0
for i in range(N) :
    for j in range(M) :
        if B[i][j] == 0 and not visit[i][j] :
            safe += 1

safe 즉 안전영역을 0으로 초기화 하고, 안전영역이면서 방문하지 않았을 경우의 칸을 계산한다.

max_safe = max(max_safe, safe)

for row, col in combination :
    B[row][col] = 0

다시 벽을 원래 상태로 되돌려서 다른 경우의 수를 탐색하도록 진행한다.

시간복잡도를 분석하면 다음과 같다.

  • combinations(cells, 3): 최대 3!(64−3)!64!≈41664 (최대 64개의 빈칸)
  • BFS: 최대 O(NM) ≈ 64
  • 최악의 경우: O(41664×64) ≈ 2.6 × 10^6 → 충분히 가능

코드

# 백준 14052 - 연구소
# 분류 : BFS, DFS

from collections import deque
from itertools import combinations

N, M = map(int, input().split())
B = [[] for _ in range(N)]

for i in range(N) :
    B[i] = list(map(int, input().split()))

cells = [(i ,j) for i in range(N) for j in range(M) if B[i][j] == 0]

max_safe = 0

for combination in combinations(cells, 3) :
    for row, col in combination :
        B[row][col] = 1
    
    # BFS
    visit = [[False] * M for _ in range(N)]
    queue = deque()

    for i in range(N) :
        for j in range(M) :
            if B[i][j] == 2 :
                queue.append((i, j))
                visit[i][j] = True
    
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    while len(queue) != 0 :
        r, c = queue.popleft()

        for i in range(4) :
            nr = r + dr[i]
            nc = c + dc[i]
            if nr < 0 or N <= nr or nc < 0 or M <= nc :
                continue
            if B[nr][nc] == 1 :
                continue
            if not visit[nr][nc] :
                queue.append((nr, nc))
                visit[nr][nc] = True
    
    safe = 0
    for i in range(N) :
        for j in range(M) :
            if B[i][j] == 0 and not visit[i][j] :
                safe += 1

    max_safe = max(max_safe, safe)

    for row, col in combination :
        B[row][col] = 0

print(max_safe)
저작자표시 비영리 (새창열림)

'Programming > 백준' 카테고리의 다른 글

백준 1316 - 그룹 단어 체커 (파이썬)  (0) 2025.02.28
백준 20922 - 겹치는 건 싫어 (파이썬)  (0) 2025.02.27
백준 6064 - 카잉 달력 (파이썬)  (1) 2025.02.25
백준 9342 - 염색체 (파이썬)  (0) 2025.02.25
백준 2015 - 수들의 합 4 (파이썬)  (0) 2025.02.24

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • 백준 1316 - 그룹 단어 체커 (파이썬)

    백준 1316 - 그룹 단어 체커 (파이썬)

    2025.02.28
  • 백준 20922 - 겹치는 건 싫어 (파이썬)

    백준 20922 - 겹치는 건 싫어 (파이썬)

    2025.02.27
  • 백준 6064 - 카잉 달력 (파이썬)

    백준 6064 - 카잉 달력 (파이썬)

    2025.02.25
  • 백준 9342 - 염색체 (파이썬)

    백준 9342 - 염색체 (파이썬)

    2025.02.25
다른 글 더 둘러보기

정보

포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

  • 포렌식 & 개발 이야기 - Forensics & Development의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

카테고리

  • Category (452)
    • Forensics (105)
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (24)
      • DFC (7)
      • 디지털포렌식전문가2급 자격증 (10)
      • FTK ACE 자격증 (7)
    • 이것저것 (7)
      • Ubuntu (6)
      • 디스코드 봇 (4)
      • Volatility GUI (2)
    • CTF (32)
      • NEWSECU (14)
      • CTF-d (5)
      • Puzzel - Network Forensics (2)
      • Security Traps (2)
      • system32.kr (5)
      • HMCTF (4)
    • Programming (260)
      • C (10)
      • Python (11)
      • 백준 (206)
      • 프로그래머스 (32)
    • 그냥 개발 및 잡담 (16)
      • Docker (2)
      • Google Cloud (3)
      • OS 개발 (3)
    • Best of Best (20)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • 포렌식
  • axiom
  • 디지털포렌식
  • 프로그래머스
  • Forensics
  • 백준
  • pental
  • 파이썬
  • 전체 보기…

정보

pental의 포렌식 & 개발 이야기 - Forensics & Development

포렌식 & 개발 이야기 - Forensics & Development

pental

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © pental.

티스토리툴바