[DFS, 기본] 백준 2667. 단지번호 붙이기

import sys
sys.stdin = open('graph input.txt', 'rt')
input = sys.stdin.readline

size = int(input())
graph = [list(map(int, input().rstrip())) for _ in range(size)]
print(graph)

apt = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
def DFS(x,y):
    global cnt
    if 0<=x<size and 0<=y<size:

        if graph[x][y] == 1:
            cnt+=1
            graph[x][y] = 0

            for i in range(4):
                nx = dx[i]+x
                ny = dy[i]+y
                DFS(nx,ny)
            return True
        return False
    else:
        return False

cnt = 0
for i in range(size):
    for j in range(size):
        if DFS(i,j) == True:
            apt.append(cnt)
            # print(cnt)
            cnt = 0
print(len(apt))
apt.sort()
for a in apt:
    print(a)

계속해서 컴포넌트 구하는 문제, cnt 변수 위치랑 조건 위치 아직도 헷갈린다.

---

\22. 10.26 보강

1. 아이디어
   2중 for문 => visited X => DFS
   DFS visited => home => 탐색
2. 시간복잡도
   단지수(V) : N**2
   연결(E) : 4*N**2
   O(V+E) : 5N**2 => N*2 => 25\*2 => 625 : 2억보다 작음
3. 자료구조
   리스트?
   visited => graph

문제 접근하는 루틴을 연습해봤다.
추가로 개선할 점 : 오름차순 정렬, heapq 써봤는데 오히려 sort()보다 시간이 더 걸렸다. 몇개 없어서 그런가보다. DFS돌리기 전에 상하좌우 돌리고 범위를 체크하는 게 시간이 덜 걸리는 것 같다. 다음에는 그렇게 풀어봐야겠다

import heapq as hq
import sys
input = sys.stdin.readline

n = int(input())
maps = [[int(s) for s in str(input().rstrip())] for _ in range(n)]
visited = [[0] * n for _ in range(n)]


def dfs(x, y, cnt):

    if 0 <= x < n and 0 <= y < n and visited[x][y] == 0 and maps[x][y] == 1:
        visited[x][y] = 1
        cnt += 1
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = x + dx, y + dy
            cnt = dfs(nx, ny, cnt)
    return cnt

result = []
cnt = 0
for i in range(n):
    for j in range(n):
        if maps[i][j] == 1 and visited[i][j] == 0:
            cnt = dfs(i, j, 0)
            hq.heappush(result, cnt)
            cnt = 1
print(len(result))
for _ in range(name):
    print(hq.heappop(result))