[백준] Python 2667번 단지번호붙이기 실버1 - 그래프

문제 : https://www.acmicpc.net/problem/2667
분류 : 그래프, 너비, 깊이 우선 탐색(BFS, DFS)

접근

1. 시작 지점을 모르니 1인 곳을 찾아 순회를 하면 된다.
2. 인접한 1의 개수를 모두 세어주고 다시 1을 찾아 여행을 떠난다.
3. 세어준 1의 개수는 모두 배열에 저장하고 저장된 수가 총 마을의 개수이다.

슈도코드

if graph == 1:
	BFS()

배열 삽입 BFS():
	q에 위치 삽입
    
    while q:
    	이동할 위치 = q에서 팝
        현재 위치 방문처리
        
        for 동서남북:
        	범위 벗어나지 않는 선에서:
            	1이고 방문한적 없으면:
                	방문처리
                    1 -> 0으로 
                    q에 삽입
                    카운트 증가
      
배열 길이 출력
배열 sort
배열 출력

풀이

from collections import deque

def solution():
    map_size = int(input()) # 지도의 크기
    graph = []
    answer = []
    for i in range(map_size):
        graph.append(list(map(int, input())))

    visited = [[False for j in range(map_size)] for i in range(map_size)]

    for i in range(map_size):
        for j in range(map_size):
            if graph[i][j] == 1:
                answer.append(BFS(map_size, graph, i, j, visited))

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

def BFS(N, graph, i, j, visited):
    # 큐 생성
    queue = deque()
    # 동 서 남 북
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    # 시작 노드 큐에 삽입
    queue.append((i, j))
    cnt_apart = 1
    # 큐가 빌 떄 까지
    while queue:
        # 현재 y, x 큐에서 꺼냄
        cur_y, cur_x = queue.popleft()
        # 방문 처리
        visited[i][j] = True

        for k in range(4):
            # 동 서 남 북 으로 이동
            next_y = cur_y + dy[k]
            next_x = cur_x + dx[k]

            # 밖으로 나가지 않고 N,M보다 크지 않을 때
            if next_y >= 0 and next_x >= 0 and next_y < N and next_x < N:
                # 해당 값이 0이 아니고 방문하지 않았을 때
                if graph[next_y][next_x] != 0 and visited[next_y][next_x] == 0:
                    # 방문 처리
                    visited[next_y][next_x] = True
                    # 인접한 노드는 가중치 증가
                    graph[next_y][next_x] = 0
                    queue.append((next_y, next_x))
                    cnt_apart += 1

    return cnt_apart

solution()