[백준 2667번] 단지 번호 붙이기 (파이썬)

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

2667번: 단지번호붙이기

먼저, 문제를 보겠습니다.

이렇콤 문제가 나와있네요.

이 문제는 DFS,BFS로 풀 수 있는데

저는 BFS를 선택해서 풀었습니다.

여러번 뻘짓을 하다가 드디어 통과되었습니다.

컴파일 에러는...

들여쓰기 잘못해서...

틀렸을 때는 왜 틀렸는지

도무지 알지 못했습니다.

그러다가 차근차근 코드를 보면서

문제를 해결해나갔습니다.

from collections import deque


def bfs(a, b):
    count = 1
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 0

    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]

    while queue:
        y, x = queue.popleft()
        # print("y=",y,"x=",x)
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if ny < 0 or ny >= N or nx < 0 or nx >= N:
                continue

            if graph[ny][nx] == 1:
                graph[ny][nx] = 0
                queue.append((ny, nx))
                count += 1
    return count


N = int(input())
cnt = []
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            cnt.append(bfs(i, j))  # 모든 그래프를 다 방문해주되, 1이 있으면 BFS시행

print(len(cnt))
cnt.sort()  # 정렬을 꼭 시켜줘야함!
for i in range(len(cnt)):
    print(cnt[i])

 

 

제가 풀었던 파이썬 코드입니다.

이전의 풀이들을 참고하여

문제를 풀었습니다.

 

이 문제에서 어려웠던 점은

 

1. BFS DFS로 길 찾기만 했지,

저렇게 구분은 어떻게 지어?

점프해?랜덤함수로 풀어?

-->아...

for 문 돌려서 그래프를

모두 방문하면 되지...

 

2. 왜 계속 틀렸다고 뜨지?

분명 다 맞았는데...

-->마지막에 cnt를 정렬 안했구나...

문제에서 정렬하라고 적혀있넹.

(이 부분은 테케로는 맞아서

찾기 어려웠던 부분.

생각해보면, 테케 이외의 경우에

3단지가 1단지보다 더 많을 수 있는데

그러면 문제에서 요구하는 답이 안됨.

문제에서 하라는 건 해야한다.)