[백준 | 파이썬3] 2667. 단지번호 붙이기-dfs활용

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

> dfs 활용

연결되어있는 격자들에 방문처리하고 개수를 카운트한다는 점에서 dfs 알고리즘을 사용하였다. 

먼저 격자 정보들을 2차원 배열형태로 입력한다. 아래 코드로 값을 입력받으면 숫자들이 모두 문자형태로 들어간다는 것을 기억하자.

그리고 격자에 방문했는지 여부를 보여주는 visited 배열과 격자의 상하좌우로 움직이기 위한 dx, dy 배열도 선언해준다.

행, 열 정보를 파라미터로 넣은 dfs 함수를 선언한다. 해당 함수에서 방문한 격자는 visited의 해당 행, 열 부분을 1로 갱신한다. 동시에 집의 개수를 세주기 위해 home+=1 해준다.

그리고 해당 격자를 대상으로 상하좌우에 위치한 격자들을 검토한다. 만일 그 격자들이 방문하지 않은 상태임과 동시에 lst에 1로 저장되어있는 격자라면 다시 해당 격자에 대해 dfs함수를 수행함으로써 연결된 격자들을 모두 검토해준다. 

다른 연결되지 않은 격자들에 대해서 검토하기 위해 격자 전체를 돌아볼 수 있도록 반복문을 설정하고 lst의 요소가 1이고 방문하지 않은 격자에 대해 dfs함수를 수행한다.

연결된 격자에 대해 모두 방문처리하면 해당 함수가 종료되고 단지 수를 카운트한다.