[백준]2667-단지

💡문제 분석 요약

-- 문제 --

입력 : N(지도 크기)

• 1은 집이 있는 곳, 0은 집이 없는 곳

• 연결된 집의 모임인 단지를 정의, 단지에 번호 붙이기

• 연결되었다는 것= 좌우, 위아래로 다른 집이 있는 경우

• 단지 수 출력, 집의 수를 오름차순으로 정렬

💡알고리즘 설계

1. input을 통해 N 입력

2. BFS

3. dfs, bfs 함수 이용

💡코드

from collections import deque

def bfs(graph, i, j):
    N = len(graph)
    need_visited = deque([])
    need_visited.append((i, j))

💡시간복잡도

O(N)

💡틀린 이유

1. 다음날 대회로 준비하는데 시간이 모자라 충분히 생각할 시간이 부족함. 대회끝나고 다시 풀어볼 예정.

💡틀린 부분 수정 or 다른 풀이

from collections import deque

def bfs(graph, i, j):
    N = len(graph)
    need_visited = deque([])
    need_visited.append((i, j))

    graph[i][j] = '0'
    num_apt = 1

    # 상하좌우 탐색
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while need_visited:
        x, y = need_visited.popleft()

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

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

            if graph[nx][ny] == '1':
                need_visited.append((nx, ny))
                graph[nx][ny] = '0'
                num_apt += 1

    return num_apt


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

cnt = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == '1':
            cnt.append(bfs(graph, i, j))

cnt.sort()
print(len(cnt))
for c in cnt:
    print(c)

💡느낀점 or 기억 할 정보

1. 처음 코테를 접하다보니 접근하는데 어려움을 느낌. -> 문제 많이 접해보기.

2. 개념만 공부하지 말고 기본 구현한 코드 많이 접해보기.

3. 다음날 대회로 준비하는데 시간이 모자라 충분히 생각할 시간이 부족함. 대회끝나고 다시 풀어볼 예정. 단지 풀이이해로 끝남.