백준, 단지 번호 붙이기

백준, 단지 번호 붙이기

 

🪴 문제

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

2667번: 단지번호붙이기

 

🪴 분류

pass

 

🪴 풀이

기본적인 dfs 문제로 풀면 된다.

상하좌우 1이고 방문한적 없는 경우 방문해줘야 한다.

방문표시를 하지 않을 경우 카운트할때 문제가 생길 뿐 아니라, 무한재귀에 빠질 수 있으니 방문표시를 해줘야 한다!

붙일 번호를 매개변수로 같이 넣어주는게 핵심!

최대한 상수 설정, global 설정해서 풀었다.

 

cnt 는 번호 붙일 번호이고, innerCnt는 1의 그룹별 갯수를 의미한다.

 

🪴 앞으로의 코드 변경 방향.

매개변수로 많이 넘길 경우 stack에 많이 쌓여 global 변수로 둘 수 있는 건 최대한 global 변수로 선언해줬다.

다음번 코드 변경할때는 함수, main나눠서 코드 작성하는 연습을 해야겠다.

 

🪴 나의 코드

N = int(input())
global maps
maps = []
for _ in range(N):
    maps.append(list(map(int, list(input()))))

visited = [[False] * N for _ in range(N)]

global dr, dc, MAX_DIRECTION, R, C
MAX_DIRECTION = 4
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
R, C = N, N

def dfs(cnt, cur_r, cur_c):
    global maps, MAX_DIRECTION, innerCnt
    innerCnt += 1
    maps[cur_r][cur_c] = cnt

    for i in range(MAX_DIRECTION):
        next_r, next_c = cur_r+dr[i], cur_c+dc[i]

        if 0<=next_r<R and 0<=next_c<C and not visited[next_r][next_c] and maps[next_r][next_c] == 1:
            visited[next_r][next_c] = True
            dfs(cnt, next_r, next_c)

cnt = 0
result = []
for r in range(R):
    for c in range(C):
        if not visited[r][c] and maps[r][c] == 1:
            visited[r][c] = True
            cnt +=1
            global innerCnt
            innerCnt = 0
            dfs(cnt, r, c)
            result.append(innerCnt)

print(cnt)
print(*sorted(result), sep='\n')