[BOJ][Python]2667번 풀이

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

2667번: 단지번호붙이기

from collections import deque
import sys
ssr = sys.stdin.readline

def sol():
    global num
    while q:
        r,c = q.popleft()
        for i in range(4):
            if 0<=r+dr[i]<n and 0<=c+dc[i]<n:
                if t[r+dr[i]][c+dc[i]] == '1' and visited[r+dr[i]][c+dc[i]] == False:
                    num += 1
                    q.append((r+dr[i],c+dc[i]))
                    visited[r+dr[i]][c+dc[i]] = True

n = int(ssr())
t = [list(ssr().rstrip()) for _ in range(n)]
visited = [[False for _ in range(n)] for _ in range(n)]
q = deque([])
dr = [-1,1,0,0]
dc = [0,0,-1,1]
ans = []
for i in range(n):
    for j in range(n):
        if t[i][j] == '1' and visited[i][j] == False:
            q.append((i,j))
            visited[i][j] = True
            num = 1
            sol()
            ans.append(num)
print(len(ans))
ans.sort()
for i in ans:
    print(i)

클래스 3에는 그래프 탐색 문제가 상당히 많이 포진 되어 있다는 느낌이 드네요. 최근에 풀었던 대부분의 문제들이 그래프 탐색인 것 같습니다. 덕분에 연습도 많이 됐지만요. 오늘 문제에서 조심해야 할 부분은 문제의 '오름차순으로 정렬해라' 입니다. 전 그걸 빼먹는 바람에 맞왜틀을 좀 시전했네요.

 

문제 접근은 일단 기본적인 bfs입니다. dfs로 풀어도 무방하실겁니다만, 알고리즘의 구조상 bfs가 조금 더 빠르겠죠. 예전에도 한번 말씀드렸던 문을 예시로 들면 가까이 있는 문들을 전부 다 열면서 가는게 하나 열고 안에 있는 문 하나 열고 또 안에 있는 문 열고 하는 것 보다 빠를테니까 말이에요(물론 컴퓨터는 우리는 상상도 못할 정도의 속도로 문을 열겠지만, 누적되는 타임 로스가 근본적으로 생길 수 밖에 없겠죠). 그런 이유 때문에 저는 bfs를 사용했습니다. 같은 단지에 해당하는 집들에 번호를 붙이는 건 진짜로 번호를 붙인다고 생각을 하면 안되고, 단지별로 구분만 가능하면 상관없다는 방식으로 접근해야합니다. 저는 ans라는 리스트의 인덱스로 단지를 구분하면 되겠다고 생각이 들었고, 그러면 그냥 갯수를 다 세어서 append시키면 해결이 가능하겠다는 결론이 나왔기 때문에 append를 이용해서 간단하게 구현해봤습니다.