2667번 단지번호붙이기

문제 설명

2667번: 단지번호붙이기

 

나의 풀이

from collections import deque


def bfs(graph, start_node):
    if graph[start_node[0]][start_node[1]] == "0":
        return False

    visited = []
    q = deque()
    q.append(start_node)
    visited.append(start_node)
    graph[start_node[0]][start_node[1]] = "0"

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

    while q:
        cur_y, cur_x = q.popleft()

        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]

            if 0 <= nx < len(graph[0]) and 0<= ny < len(graph) and graph[ny][nx] == "1":
                if (ny, nx) not in visited:
                    graph[ny][nx] = "0"
                    visited.append((ny, nx))
                    q.append((ny, nx))

    return visited


n = int(input())
graph = [list(input()) for _ in range(n)]

cnt = 0
answer = []
for i in range(len(graph)):
    for j in range(len(graph[0])):
        if graph[i][j]:
            result = bfs(graph, (i, j))
            if result:
                cnt += 1
                answer.append(len(result))
print(cnt)
answer.sort()
for i in answer:
    print(i)

문제 요약: 섬의 갯수를 구하고 각 섬의 넓이를 오름차순으로 반환하는 문제

1) BFS로 각 섬의 넓이를 구하는 함수를 설정, 그리고 지나온 점들은 방문기록 리스트에 추가하고 방문했던 좌표를 "0"으로 바꾼다.
     그리고 시작 점이 '0'일 때에 대한 예외처리를 해준다. 모든 점들을 방문해서 섬의 갯수를 세어야하므로! 

2) 모든 점들을 방문하여 bfs에 들어가는 섬의 갯수를 구하고, 각 섬의 넓이를 answer리스트에 추가 

3) 오름차순으로 정렬 후 반환

 

코드의 잡음을 줄여보자!

from collections import deque


def bfs(graph, start_node):
    if graph[start_node[0]][start_node[1]] == "0":
        return False

    q = deque()
    q.append(start_node)
    graph[start_node[0]][start_node[1]] = "0"

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

    house_cnt = 1
    while q:
        cur_y, cur_x = q.popleft()

        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]

            if 0 <= nx < len(graph[0]) and 0<= ny < len(graph) and graph[ny][nx] == "1":
                house_cnt += 1
                graph[ny][nx] = "0"
                q.append((ny, nx))

    return house_cnt


n = int(input())
graph = [list(input()) for _ in range(n)]

cnt = 0
answer = []
for i in range(len(graph)):
    for j in range(len(graph[0])):
        result = bfs(graph, (i, j))
        if result:
            cnt += 1
            answer.append(result)
            
print(cnt)
answer.sort()
for i in answer:
    print(i)

 bfs 함수의 visited 리스트를 없애고 집의 갯수를 구하는 변수를 설정, 리스트 값이 방문했다면 '0'으로 변하기에 굳이 방문기록을 만들 필요가 없다고 생각함. 따라서 bfs안에 조건 식이 단조로워 졌고, 같은 번지 내에 집의 갯수를 구하는 함수로 좀 더 명확한 값이 반환이 된다. 

또한, 아래 result를 구하는 함수에서 따로 0과 1을 구분할 필요가 없다. bfs 함수에서 이를 구분하여 리턴 해주기 때문. 전체 식이 좀 더 직관적으로 변한걸 확인할 수 있다.