백준 2667 파이썬(DFS/BFS)

DFS문제다.

DFS/BFS 탐색문제를 계속해서 풀면서 느끼는건

 

1. 방문했던 곳을 한번더 방문하지 않기 위해서 적절한 표시를 남기는 방법

2. DFS는 재귀를 이용해서 BFS는 큐를 이용해서 푼다.

 

이 두가지를 고려하면서 문제를 풀기 시작하면 어느정도 풀리는 것 같다.

 

처음에는 DFS문제이므로 주어진 값들을 그래프로 그려보고 노드라고 보고 문제를 풀어보려고 했었다.

그런데 자기 자신으로 이어지는 노드들을 고려하는게 생각보다는 까다로웠다.

그래서 그냥 그래프, 노드 이런 개념들은 잠시 접어두고 2차원 배열 그 자체로 보고 문제를 풀기 시작했다.

 

먼저는 dfs함수를 정의했다.

주어진 좌표평면에서 벗어나지 않으면서

숫자가 1인 곳들을 표시하면서 탐색하는 함수를 만들었다.

 

그리고 표시를 할 때 각 단지별로 서로다른 숫자가 붙을 수 있게끔 만들었다.

 

마지막으론 단지별 아파트의 숫자를 세기위해서 반복문을 세개나 같이 썻다.

(사실 이 코드를 짜면서 반복문을 이렇게 많이 쓰면 또 시간초과가 뜨는건 아닐지 걱정이 되긴 햇지만..)

 

코드내용

# 2667 단지번호붙이기

# 입력값
n = int(input())
# 그래프
graph = []
for _ in range(n):
    graph.append(list(map(int,input())))

# dfs함수 정의
def dfs(x,y,apt_num):
    if x < 0 or x > n-1 or y < 0 or y > n-1:
        return False
    if graph[x][y] == 1:
        graph[x][y] = apt_num
        dfs(x,y+1,apt_num) # 상
        dfs(x,y-1,apt_num) # 하
        dfs(x-1,y,apt_num) # 좌
        dfs(x+1,y,apt_num) # 우
        return True
    else:
        return False

# 단지의 개수, 단지별 서로다른 숫자 할당하기
result = 0
apt_num = 2 
for x in range(n):
    for y in range(n):
        if dfs(x,y,apt_num) == True:
            apt_num += 1
            result += 1

# 아파트 단지별로 아파트 숫자 카운트
homes = []
for apt_num in range(2,result+2):
    count = 0
    for i in graph:
        for j in i:
            if apt_num == j:
                count += 1
    homes.append(count)
homes.sort()   

# 결과 출력
print(result)
for i in homes:
    print(i)