[코드트리 챌린지](4주차) DFS_마을 구분하기

문제:

문제 링크: https://www.codetree.ai/missions/2/problems/seperate-village?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

풀이:

dfs 개념 설명을 보고나서 이 문제를 풀어보려고 했는데 dfs와 어떤 상관이 있는지 처음에는 잘 연결짓지 못했다.

하지만 dfs 개념의 코드를 잘 보고 풀이 과정을 생각해보니 재귀함수와 visited 배열을 사용하여 이 문제도 풀면 될 것 같았다. 사실 해설을 좀 참고 했다. ㅋ 하지만 다음엔 풀 수 있을 듯?

 

코드:

n = int(input())
vill = [
    list(map(int, input().split()))
    for _ in range(n)
]
visited = [[False]*n for _ in range(n)]

dxs = [0, +1, 0, -1]
dys = [-1, 0, +1, 0]

people_num = 0
people_nums = []

def can_go(x, y):
    if x >= 0 and x < n and y >= 0 and y < n:
        if not visited[x][y] and vill[x][y] != 0:
            return True
    return False

def dfs(x, y):
    global people_num
    for dx, dy in zip(dxs, dys):
        nx = x + dx
        ny = y + dy

        if can_go(nx, ny):
            visited[nx][ny] = True
            people_num += 1

            dfs(nx, ny)

for i in range(n):
    for j in range(n):
        if can_go(i, j):
            visited[i][j] = True
            people_num = 1
            dfs(i, j) 
            people_nums.append(people_num)

people_nums = sorted(people_nums)

print(len(people_nums))
for p in people_nums:
    print(p)

 

---

실력진단 결과:

ㅠㅠ 다시 떨어졌다.

그 재귀함수 써서 숫자 만드는 똑같은 문제를 이번엔 못 풀어버렸다.

다음엔 그걸 다시 공부해야겠다.