[백준] 2667 단지 번호 붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

def find_adjacent(matrix, node):
    # node = (row, col)
    _list = []
    delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] #상하좌우
    for dt in delta:
        tmp_row = node[0] + dt[0]
        tmp_col = node[1] + dt[1]
        if 0 <= tmp_row < len(matrix) and 0 <= tmp_col < len(matrix):
            if matrix[tmp_row][tmp_col] == '1':
                _list.append((tmp_row, tmp_col))
    return _list


n = int(input())
apart_complex = [input() for _ in range(n)]
visited = [[0]*n for _ in range(n)]
stack = []
num_of_apart = []
count = 1
danji = 1
for r in range(n):
    for c in range(n):
        if apart_complex[r][c] == '1' and visited[r][c] == 0:
            #print(r,c)
            stack.append((r, c))
            while stack:
                visit_node = stack[-1]
                visited[visit_node[0]][visit_node[1]] = danji
                adjacent_graph = find_adjacent(apart_complex, visit_node)
                #print(adjacent_graph)
                for adjacent in adjacent_graph:
                    if not visited[adjacent[0]][adjacent[1]]:
                        count += 1
                        stack.append(adjacent)
                        break
                else:
                    stack.pop()
            else:
                num_of_apart.append(count)
                count = 1
                danji += 1
else:
    danji -= 1

print(danji)
for num in sorted(num_of_apart):
    print(num)

 

dfs를 너무 길게 짜긴 했는데 꽤나 할만하다. 2차원이라 길다고 생각하자

다른 사람의 코드를 보니까 dfs 자체를 함수로 구현하던데 아직 내 실력이 부족한듯하다

---

공부를 위해 타인의 DFS 코드도 같이 첨부해놓는다.

dx=[-1,0,1,0]
dy=[0,1,0,-1]
n=int(input())
a=[input() for _ in range(n)]
cnt=0
apt=[]

def dfs(x,y):
    global cnt
    a[x][y] = '0' #방문한 곳은 0으로
    cnt+=1
    for i in range(4):
        nx = x + dx[i] #i=0일때 (nx,ny)는 좌 , i=1일때 (nx,ny)는 상
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >=n:
            continue
        if a[nx][ny] == '1':
            dfs(nx,ny)

for i in range(n):
    for j in range(n):
        if a[i][j] == '1':
            cnt= 0
            dfs(i,j)
            apt.append(cnt)

이 코드에서 볼만한 것은 세 가지이다.

첫 번째, 이차원 배열이라 델타를 썼고 범위가 넘어가는 부분에 대해서는 넘어갔다. 이건 나랑 비슷하다. ㅎㅎ

두 번째, 방문한 곳을 0으로 바꾸어서 가지 못하게 만들어놓았다. 메모리를 아낄수 있는 좋은 방법같은데 문제에 따라 생각해봐야할듯하다. 나는 visited라는 이차원 배열을 만들어서 체크했다.

세번째, 방문하지 않은 노드(r,c)를 찾으면 재귀로 다시 찾는다. 오늘 배웠던 백트래킹도 약간 이런식인데 재귀함수로 짜는게 쉬운거같으면서도 어렵다. 나중에 복습하면서 한번더 해봐야겠다.