김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 2638 치즈 파이썬(Python)

문제 링크

평범한 시뮬레이션 문제인데, 한 가지 재밌는 부분은 치즈로 인해 막힌 공간을 구해야 한다는 점이다.
가장자리는 반드시 뚫린 공간이기 때문에, 임의의 가장자리(이를테면 0,0)에서 시작해서 탐색을 하면 빈 공간을 구할 수 있다.
주의할 점은, 치즈가 녹아서 새로운 공간이 생길 때마다 탐색을 다시 수행해주어야 한다는 것 정도가 있다.

from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)
input = stdin.readline

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]

# 치즈의 위치를 저장하고 있는 집합
cheese = set()
for i, line in enumerate(board):
	for j, e in enumerate(line):
		if e == 1:
			cheese.add((i, j))

# 격자의 가장자리에서 dfs 후 남은 공간은 치즈 내부 공간
def dfs(x, y):
    if visited[x][y] or board[x][y]:
        return
    visited[x][y] = 1
    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if 0<=x+dx<n and 0<=y+dy<m:
            dfs(x+dx, y+dy)

# t는 시간
t = 0
# 가장자리 임의의 공간(0, 0)에서 DFS
dfs(0, 0)
while cheese:
    t += 1
    # 한번 순회를 돈 이후 한번에 치즈를 제거하기 위해 차집합을 사용했다
    removeSet = set()
    for i, j in cheese:
        temp = 0
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            if visited[i+di][j+dj] == 1:
                temp += 1
        if temp >= 2:
            removeSet.add((i, j))
            board[i][j] = 0
    cheese -= removeSet
    for i, j in removeSet:
        dfs(i, j)

print(t)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑