✅ 오늘의 학습 키워드
- DFS (깊이 우선 탐색)
- 단절점 (Articulation Point)
- 그래프 연결성 판별
✍️ 공부한 내용 본인의 언어로 정리하기
오늘은 백준 31464번 초콜릿 괴도 코코 문제를 풀어보았다. 이 문제는 단일 덩어리로 연결된 초콜릿 중, 하나를 떼었을 때 여전히 연결된 상태를 유지하면서 단절점이 생기게 되는 칸들을 찾는 것이 목표였다.
핵심은 다음과 같다:
1. 특정 칸을 하나 제거한 뒤에도 전체가 연결되어 있어야 하고,
2. 그 상태에서 임의의 두 칸을 자르면 정확히 두 조각으로 나뉘어야 한다. (즉, 단절점이 존재해야 함)
그래서 다음 절차로 풀고자 했다:
- 하나씩 초콜릿 칸을 떼어가며 DFS로 연결성을 체크
- 연결된 경우, Tarjan’s 알고리즘을 적용해 단절점을 탐색
- 단절점이 있다면 해당 칸을 정답 후보로 저장
🧠 오늘의 회고
어떤 문제가 있었고, 나는 어떤 시도를 했는지
- DFS로 연결된 칸을 검사하고, 단절점까지 잘 탐색했지만 백준에서 계속 출력 초과(RunTimeError: Output Limit Exceeded)가 발생했다.
어떻게 해결했는지
- 여러 가지 시도를 해보았고, DFS의 탐색 경계를 줄이거나 방문 조건을 타이트하게 했지만 문제 해결에 실패했다.
- 특히 연결 체크와 단절점 판별을 두 번 반복하면서 너무 많은 출력을 발생시켰거나, 잘못된 좌표를 정답으로 출력한 것이 원인일 수 있다고 의심된다.
무엇을 새롭게 알았는지
- 단절점(articulation point)을 다룰 때, 한 연결 컴포넌트 내에서만 정확히 탐색해야 하며, 모든 칸을 정답처럼 출력하면 안 된다는 점을 다시금 깨달았다.
- 출력 초과는 출력 값이 많은 경우뿐 아니라, 틀린 값이 너무 많이 출력되면 생기는 경우도 있음을 알게 되었다.
내일 학습할 것은 무엇인지
- Tarjan 알고리즘 복습 및 단절점 탐색을 보다 효율적으로 수행하는 방법 정리
- 출력 초과 관련 디버깅 팁 정리 및 출력 조건을 더 엄격하게 적용하는 방법
📝 작성한 코드 (부분)
import sys
N = int(input())
grid = [list(input().strip()) for _ in range(N)]
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
def in_range(x, y):
return 0 <= x < N and 0 <= y < N
# dfs로 연결된 칸 수 세기
def dfs(x, y, visited, erased):
visited[x][y] = True
count = 1
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if in_range(nx, ny) and not visited[nx][ny] and grid[nx][ny] == '#' and (nx, ny) != erased:
count += dfs(nx, ny, visited, erased)
return count
# 단절점 찾기 (Tarjan 알고리즘)
def articulation_points(erased):
idx = [[-1]*N for _ in range(N)]
low = [[-1]*N for _ in range(N)]
visited = [[False]*N for _ in range(N)]
counter = [0]
result = set()
def dfs_ap(x, y, px, py, root):
visited[x][y] = True
idx[x][y] = low[x][y] = counter[0]
counter[0] += 1
children = 0
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if not in_range(nx, ny) or grid[nx][ny] != '#' or (nx, ny) == erased:
continue
if not visited[nx][ny]:
dfs_ap(nx, ny, x, y, False)
low[x][y] = min(low[x][y], low[nx][ny])
if not root and low[nx][ny] >= idx[x][y]:
result.add((x, y))
children += 1
elif (nx, ny) != (px, py):
low[x][y] = min(low[x][y], idx[nx][ny])
if root and children >= 2:
result.add((x, y))
for i in range(N):
for j in range(N):
if grid[i][j] == '#' and (i, j) != erased:
dfs_ap(i, j, -1, -1, True)
return result
return set()
# 전체 초콜릿 수 세기
total = sum(row.count('#') for row in grid)
answer = []
for i in range(N):
for j in range(N):
if grid[i][j] != '#':
continue
# 초콜릿을 떼어낸 후 연결 확인
visited = [[False]*N for _ in range(N)]
found = False
for x in range(N):
for y in range(N):
if grid[x][y] == '#' and (x, y) != (i, j):
size = dfs(x, y, visited, (i, j))
found = True
break
if found:
break
# 하나의 연결된 덩어리가 아니라면 스킵
connected = True
for x in range(N):
for y in range(N):
if grid[x][y] == '#' and (x, y) != (i, j) and not visited[x][y]:
connected = False
if not connected:
continue
# 단절점 검사
aps = articulation_points((i, j))
if aps:
answer.append((i + 1, j + 1))
# 출력
print(len(answer))
answer.sort()
for x, y in answer:
print(x, y) #99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
