[코드트리 챌린지] 5주차 - 그래프 탐색(DFS)

★ 핵심 : DFS(깊이우선탐색)

https://www.codetree.ai/cote/13/problems/seperate-village?&utm_source=clipboard&utm_medium=text 

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

· 핵심

1. 각 마을의 위치를 찾기 위해 전체 board영역에 이중for문 돌면서 '벽이거나 이미 방문한 곳'을 제외하고 DFS 진행

→ global cnt 도입하는 대신 cnt(사람의 수)를 dfs 내에서 초기화하고 return값으로는 누적되는 cnt값 출력

→ dfs 함수 종료되고 변수 cnt에 누적된 사람 수 넣고 cnts에 모으기

 

2. is_vaild()에서 판단할 것들 

→ 0 <= r < n & 0 <= c < n, r과 c 가 적절한 좌표값인지 

→  in_queue[r][c] 가 False, 즉 방문 하지 않은 곳인지

→  board[r][c] == 1, 이동 가능한 곳인지

---

· 코드(Python)

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)]

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

def is_valid(r, c):
    return 0 <= r < N and 0 <= c < N and not visited[r][c] and board[r][c] == 1

def dfs(cr, cc):
    visited[cr][cc] = True
    cnt = 1 

    for k in range(4):
        nr = cr + dr[k]
        nc = cc + dc[k]
        if is_valid(nr, nc):
            cnt += dfs(nr, nc)

    return cnt

cnts = []
for r in range(N):
    for c in range(N):
        if visited[r][c] or board[r][c] == 0:
            continue
        cnt = dfs(r, c)
        cnts.append(cnt)

print(len(cnts))
for x in sorted(cnts):
    print(x)

 

※ 실력진단

PS. 정보처리기사 10월 7일날 마무리했다. 그래서 코딩테스트는 하나도 신경 쓰지 못했다. 열심히 해야지라는 마인드로 호기롭게 블로그챌리진 도전했는데 점수는 더 떨어지고 아쉬운 마음만 크다. 이번 주에는 그래도 저번 주보다 조금이라도 아주 조금이라도 더 공부하자.