[코드트리 - 연습/dfs, bfs] 마을 구분하기

요즘 코드트리로 사람들이 코딩 공부 많이 하는 것 같아서, 공부 플랫폼을 옮겨봤다.

 

시작하며 레벨 테스트를 하는데 DFS, BFS부터 막혀서 20분째 끙끙댔다...

 

https://www.codetree.ai/missions/2/problems/seperate-village/discussions

 

미래에셋도 그렇고 삼성도 그렇고 DFS, BFS 코드는 외워서 칠 수 있다는 자부심 하나로 살아왔는데, 그렇지 않은 것 같아 현타가 줄줄 났다.

 

그래서 이번에는 dfs를 재귀가 아닌 반복문 활용해서 구현한 코드를 소개하고자 한다.

n = int(input())
graph = [list(map(int,input().split())) for _ in range(n)]
visited = [[-1] * n for _ in range(n)]


def dfs(x,y):
    visited[x][y] = 1
    count = 1
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    stack = []
    stack.append((x,y))
    while stack:
        n_x,n_y = stack.pop()
        for i in range(4):
            nx = n_x + dx[i]
            ny = n_y + dy[i]
            if 0<= nx < n and 0 <= ny <n:
                if visited[nx][ny] == -1 and graph[nx][ny] == 1:
                    stack.append((nx,ny))
                    visited[nx][ny] = 1
                    count += 1
    return count
village = []
# count = 0
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1 and visited[i][j] == -1:
            people = dfs(i,j)
            # count += 1
            village.append(people)
village.sort()
print(len(village))
for i in range(len(village)):
    print(village[i])

 

 

진단평가에서 틀린 이유가 뭘까..

 

세상이 나를 억까한 게 아닐까 했는데, 내가 자초한 실수에 그딴 건 없었다.

 

반복문을 사용할 때 방문 체크를 할 때 visited 넣는 것을 안한 게 실수였다.

 

다음엔 이런 실수 절대 하지 않도록 주의해야겠다.