[DFS] BOJ_2667 단지번호붙이기
문제
https://www.acmicpc.net/problem/2667
풀이 방법
Vacuous truth: 공진리
가정이 모순이라면 주장이 무엇이든 상관없이 참이 되는 것.
연결된 집들의 모임: 단지
연결됨: 어떤 집이 상||하||좌||우로 연결되어있는 경우
집이 1개일때가 단지인지 아닌지 알 수 없으니 집이 1개일때도 단지라고 보았다.
소스코드
n = int(input())
graph = [[0] * n for _ in range(n)]
can_visit = 0
# 그래프 입력
for i in range(n):
tmp = input()
for j in range(n):
graph[i][j] = tmp[j]
if tmp[j] == '1':
can_visit += 1
# 단지 정하기
# 1) 단지: 연결된 집들의 모임
# 2) 연결된 집: 상,하,좌,우
# 3) 순회: DFS
dy = [1, -1, 0, 0]
dx = [0, 0 , 1, -1]
visited = [[False] * n for _ in range(n)]
cnt_visited = 0
# 전체를 다 순회할때까지
def dfs(start, num):
stack = [start]
cnt = 0
while stack:
y, x = stack.pop()
if not visited[y][x]:
visited[y][x] = True
cnt += 1
# print(f"({y}, {x})")
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if 0 <= ny< n and 0 <= nx < n:
if not visited[ny][nx] and graph[ny][nx] != '0':
graph[ny][nx] = num
stack.append((ny, nx))
return cnt
num = 0
danji = []
for i in range(n):
for j in range(n):
# if cnt_visited == can_visit:
# break
if not visited[i][j] and graph[i][j] == '1':
num += 1
cnt = dfs((i, j), num)
danji.append(cnt)
cnt_visited += cnt
# 그래프 출력
# 각 단지에 속하는 집의 수를 오름차순 정렬해서 출력
danji.sort()
print(len(danji))
for d in danji:
print(d)
Author And Source
이 문제에 관하여([DFS] BOJ_2667 단지번호붙이기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@superyodi/DFS-BOJ2667-단지번호붙이기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)