[백준] 2667 단지번호붙이기 (실버1) / DFS

문제요약

나의 코드 및 설명

• dfs을 통해 지도에서 붙어있는 집(1)의 개수를 카운트할 수 있다.
• 이 때, 집의 개수를 카운트할 때마다 해당 좌표에 해당하는 집을 없애면서(0) 카운트한다.
• dfs을 만들었으면, 메인함수에서 지도의 좌표 값이 1인 곳에서 dfs를 호출한다.

def dfs(x,y):
    global count
    board[y][x] = 0
    count += 1 #호출 되었을 때 카운트

    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if nx<0 or ny<0 or nx>=n or ny>=n:
            continue
        else:
            #호출 가능한 조건
            if board[ny][nx] == 1 and visited[ny][nx] == 0:
                dfs(nx, ny)


n = int(input())
board = []
for _ in range(n):
    board.append(list(map(int, str(input()))))
visited = [[0]*n for _ in range(n)]
count = 0
ans = []

dx = [0,1,0,-1]
dy = [1,0,-1,0]

for j in range(n):
    for i in range(n):
        if board[j][i] == 1:
            dfs(i,j)
            ans.append(count)
            count = 0

ans.sort()

print(len(ans))
for i in ans:
    print(i)

 

피드백

본래에는 for문 안에서 하위 함수를 호출하기 전에 카운트를 해주었다. 이렇게 했는데도 예제 출력값은 제대로 나왔으나 이상하게 틀렸다는 판정을 받았다.. 풀이를 참고하여 dfs가 호출되고 나서 카운트를 해주도록 코드를 수정하였더니 정답 판정을 받을 수 있었다. 

처음 작성했던 코드.. for문안에서 count를 증가시키고 좌표의 끝에 도달했을 때 리턴하였다.

풀이를 참고하여 수정한 코드.. dfs가 호출되었을 때 count를 증가시킨다. 별도의 리턴 없이도 count 값이 저장된다.