백준 2667 문제 풀이 python

🐒 단지번호붙이기

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

✍ 나의 풀이

import sys



n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

house = 0

def dfs(x,y):
    global house
    if x<0 or x>=n or y<0 or y>=n:
        return False

    if graph[x][y] == 1:
        graph[x][y] = 0
        house += 1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        return True
    return False

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

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

DFS 알고리즘은 잘 사용했지만,
방문한 노드의 갯수를 세는데에서 막혔다.

전역변수를 사용해야겠다는 아이디어는 떠올렸지만 막상 사용법을 몰라서 다른 사람의 풀이를 참고했다.

참고한 풀이

---

🧠 문제 이해

DFS 알고리즘으로 상하좌우로 붙어있는 집 찾아서 방문처리

한집 방문할때마다 전역변수에 1씩 더하기

각 단지에 속하는 집의 수를 오름차순으로 정렬후 출력

import sys



n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))
# nxn 2차원 그래프 배열 채우기


house = 0
 # 방문한 집 갯수를 저장할 변수를 초기화

def dfs(x,y):
    global house	# 전역변수 불러오기
    if x<0 or x>=n or y<0 or y>=n:
        return False
        	# 그래프 배열 범위 벗어날시 함수종료

    if graph[x][y] == 1:
        graph[x][y] = 0 # 방문처리
        house += 1	 # 방문한 집 갯수 +1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y-1)
        dfs(x,y+1)
        
        # 상하좌우 집 방문
        
        return True
        	# 단지의 마지막 집 방문하면 True값 반환
    return False

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

print(len(result))
result.sort() # 각 단지에 속하는 집의 수를 오름차순으로 정렬후 출력
for i in result:
    print(i)

---

좀 더 간단하게 코딩할 수 있을듯!