[코드트리 조별과제] DFS / 마을 구분하기 파이썬 풀이(Python)

 

오랜만에 다시 코드트리 진단테스트를 봤는데 말이죠..........

 

DFS/BFS에서 막힘(시간 부족 이슈...... 20분의 제한이 있었는데 그 안에 못햇어욥,,)

아니 왜임.... 그 문제를 다시 풀어보고 싶은데 확인할 수 있는 방법을 못찾아서ㅠ 못봤답니다?ㅠ

만약 코드트리 진단평가 틀린 문제를 다시 보는 법을 아신다면... 댓글 부탁드려요🥺

 

아무튼~! 그래서 이번주는 DFS를 다시 해보기로 했습니다..ㅎ.ㅎ....

왜냐면 .. 그 문제를 DFS로 시도했었는데, 런타임에러 나고 그랬어서,, DFS를 더 연습해야겠다 싶더라고요... (왠지 BFS로 고쳤으면 맞았을 것 같은데 바꾸다가 시간이 끝나부렀스ㅠ)

 

DFS

DFS는 뭐냐~ Depth First Search의 약자로, 깊이 우선 탐색을 의미합니다~

그래프 안에서 연결된 노드들이 있잖아요? 그럼 각 노드들을 하나씩하나씩 보고 넘어가는게 아니라, 하나를 보고, 그 안에 들어가 연결된 것들 중 또 하나 보고.... 이런식으로 타고타고 들어가는 것이다~

 

이때 dfs도 그렇고, bfs도 그렇고 방문했는지 여부를 체크할 필요가 있습니다.

왜냐면 체크하지 않으면 그 곳을 계속 탐색하게 될테니까요!

 

여기서 배운 점

BFS 탐색에서는 꼭 queue에 넣기 전에 visited 배열에 방문 표시를 해야 하므로, 가능하면 DFS 탐색 시에도 재귀 함수 호출 직전에 visited 표기를 하는 패턴으로 연습을 하는 것을 강력 추천

 

그렇다네요... 그냥 간단간단하게 하려고 종종 호출 후에 visited를 하는 패턴을 썼었는데.. 거기서 문제가 있었던 것 같기도?!

 

[문제] 마을 구분하기

이게 제가 틀렸던 문제의 유사 문제입니다...ㅎ... 내가 푼 문제는 주어진 위치들이 서로 다른 마을이냐 여부 찾는 거엿음

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

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

하하 코드트리에서 블로그 공유하는 법^^ 이라는 걸 이제야 확인해서, 이렇게 공유합니닷

 

예시입출력

입력	출력
5 1 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1	4 2 3 4 6

 

풀이(Python)

import sys
input=sys.stdin.readline
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]

ans=0
dr,dc=[0,1,-1,0],[1,0,0,-1]
def dfs(r,c):
    cnt=1
    for i in range(4):
        nr,nc=r+dr[i],c+dc[i]
        if 0<=nr<n and 0<=nc<n and arr[nr][nc]==1:
            arr[nr][nc]=0
            cnt+=dfs(nr,nc)
    return cnt

ans=0
vil=[]
for i in range(n):
    for j in range(n):
        if arr[i][j]==1:
            ans+=1
            arr[i][j]=0
            vil.append(dfs(i,j))
print(ans)
for x in sorted(vil):
    print(x)

 

개수 세기를 dfs에서 어떻게 하나~ 생각했지만...! 1개씩 더한다는 생각으로 했습니당

 

배운 점

1. 개수 세기를 visited처리하듯, 들어갈때마다 +1해주는 방식도 있다!

2. 파이써닉하게 방향 배열 빼는 법... zip 사용하기 => 엄청나게 편한 건 아니지만, 이런 방법도 있다!

for dx, dy in zip(dxs, dys):
    new_x, new_y = x + dx, y + dy