[Algorithm] 백준 #2667 - 단지번호붙이기

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

2667번: 단지번호붙이기

 

📌 다시 봐야 할 부분

1. 다른 문제와 조금 달랐던 점은, (bfs방식) 큐에 값을 넣고 하나씩 꺼내고 확인과정에서 연결된 지점의 갯수도 구하고, 연결된 지점이 몇개의 칸으로 이루어져 있는지도 함께 구해줘야 했다. 

 

주로 지금까지 풀때는 bfs함수를 구성할때 리턴값이 없었는데, 이 문제에서는 graph의 값이 1일때마다

값을 0으로 바꿔주고(방문처리) + 큐에 추가하고 + 갯수 세주기(count변수 증가)

위의 과정을 모두 적어주었다. 

 

2. 그리고!! 매번 자꾸 헷갈린다.

for문안에서 범위를 벗어난 곳일때는 continue를 수행하는데, 범위를 벗어나는 기준이

nx<0 or nx>=n or ny<0 or ny>=n 이다!(등호가 들어가야 한다!!)

인덱스 번호는 0부터 시작하기에, 크기가 n X n이라고 해도 실제 값은 0 ~ (n-1)이 들어가기에 n이 되면 범위에서 벗어난 것이다. 그리고 x,y좌표가 자꾸만 헷갈린다... 내가 매번 생각하는 것과 반대이다. 이젠 알자 ^^

아래 사진처럼 증가한다.

 

 

 

 

 

 

 

# bfs
from collections import deque
import sys
dx = [0, 0, 1, -1]  // 상하좌우 연결 지점 확인을 위한 리스트
dy = [1, -1, 0, 0]

def bfs(graph, x, y):
    n=len(graph)
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0  # 맨 처음 지점도 방문처리
    count = 1  # 처음 값도 갯수에 카운트 반드시 해주기!

    while queue:  # 큐가 빌때까지 반복
        x, y = queue.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx<0 or nx>=n or ny<0 or ny>=n:  # 범위를 벗어난 경우
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0   #값을 0으로 바꿔준다
                queue.append((nx, ny))
                count += 1
    return count  # 몇개로 구성되었는지 리턴


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

nums = []
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:  # 값이 1인 경우에 멈춰서 bfs함수 수행
            nums.append(bfs(graph, i, j))  # 몇개로 구성되었는지 nums배열에 넣기
            # print(nums)
nums.sort()  # 정렬해서 출력
print(len(nums))
for i in range(len(nums)):
    print(nums[i])