2667_단지번호붙이기

2667번: 단지번호붙이기 (acmicpc.net)

2667번: 단지번호붙이기

접근 방법

상하좌우를 모두 돌며 집이 연결되어 있는지 확인 -> DFS 사용 

1. 노드 == 1이면 0으로 변경하고 상, 하, 좌, 우 확인 후 return True

2. 노드 == 0 이면 return False 

3. global 변수를 사용하여 상하좌우 확인할 때 집의 개수 추가 

 

주의 할 점 

1. 상하좌우를 확인 할 때 범위를 넘어갈 수 있으므로 미리 예외 처리 하기 

2. graph 값 int 로 변환하기 

 

정답 코드 

# dfs
# 1. 단지 수 세기
# 2. 단지 내 집의 개수를 오름차순 출력

# 입력 받기
n = int(input())
graph = []
for _ in range(n):
    graph.append(list(input()))

# 단지 내 집의 수 계산 변수
cnt = 0
# 결과를 담을 리스트
result = []

def dfs(x,y):
    global cnt
    # 예외처리
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    # 1이면 방문
    if int(graph[x][y]) == 1:
        cnt += 1
        # 방문 처리
        graph[x][y] = 0
        dfs(x, y - 1)
        dfs(x, y + 1)
        dfs(x - 1, y)
        dfs(x + 1, y)
        return True
    return False

for i in range(n):
    for j in range(n):
        if dfs(i, j):
            result.append(cnt)
            cnt = 0

result.sort()
print(len(result))
for i in result:
    print(i)