2667번: 단지번호붙이기

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

 

이 문제를 풀기 위한 아이디어를 다음과 같이 설정했다.

1. BFS를 사용한다

2. 그래프를 생성한 후, 모든 노드마다 방문한 적이 없다면 해당 노드를 start로 설정하여 BFS를 수행한다

 

그리고 단지 별 단지 수는 dictionary를 사용하여 답을 내도록 했다.

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

import sys
from collections import defaultdict, deque

N = int(input())
MAP = []
graph = defaultdict(list)

for i in range(N) :
    MAP.append(input())

# graph 만들기
for i in range(N) :
    for j in range(N) :
        if MAP[i][j] == '1' :
            graph[(i, j)].append((i, j))
            if j >= 1 : # left
                if MAP[i][j-1] == '1' :
                    graph[(i, j)].append((i, j-1))
            if j < N-1 : # right
                if MAP[i][j+1] == '1' :
                    graph[(i, j)].append((i, j+1))
            if i >= 1 : # up
                if MAP[i-1][j] == '1' :
                    graph[(i, j)].append((i-1, j))
            if i < N-1 : # down
                if MAP[i+1][j] == '1' :
                    graph[(i, j)].append((i+1, j))

visited = [[0 for _ in range(N)] for _ in range(N)]
ans = defaultdict(list)
def BFS(start, graph, visited, num, ans) :
    q = deque([(start)])
    visited[start[0]][start[1]] = num
    ans[num].append(start)
    while q :
        u = q.popleft()
        visited[u[0]][u[1]] = num
        ans[num].append(u)
        for v in graph[u] :
            if visited[v[0]][v[1]] == 0 :
                visited[v[0]][v[1]] = num
                q.append((v))
                ans[num].append(v)
    ans[num] = list(set(ans[num]))
    return num + 1

num = 1
for key in graph :
    if visited[key[0]][key[1]] == 0 :
        num = BFS(key, graph, visited, num, ans)

print(len(ans))
ans = sorted([len(ans[k]) for k in ans])
for _ in ans :
    print(_)

• num으로 ans dictionary에 단지 별 단지 수를 기록한다.
• 중복되는 노드의 경우 ans[num]을 한번 집합(set)으로 변환시켜 없앤다.

이번 문제에서 내가 놓쳤던 반례는 다음과 같다.

https://www.acmicpc.net/board/view/146481

단지 별로 단지 수가 1일 경우 그래프에 저장이 되지 않았다.

그래서 graph 생성 시, 

# graph 만들기
for i in range(N) :
    for j in range(N) :
        if MAP[i][j] == '1' :
            graph[(i, j)].append((i, j))

MAP[i][j] == '1'일 경우, graph에 추가하도록 했다.