백준 2267번. 단지번호 붙이기 (파이썬 DFS이용)

문제를 요약하면..

요소개수 구하는 문제와 동일하다!

1. 1로 묶여저있는 요소의 갯수 및 묶음의 갯수 구하기

  -묶음의 갯수 = 단지 갯수  -> house 리스트에 저장 후 리스트 길이로 치환

 -요소의 갯수 = 단지별 집의 갯수  = count  -> DFS 탐색이 가능할 때마다 count++

2. 방문했다면 흔적을 남겨야 한다. -- 2-1, 2-2 사용한 2가지 방법 해봄!!

2-1) 방문 여부 True/False를 저장하는 visited 리스트에서 True로 저장

2-2) 별도 visited 리스트 없이 그래프에서 바로 1->0으로 바꾸기

2-3) 2-1 & 2-2 둘다 쓰기 --다른 풀이보면 가끔 보이는데..굳이 할 필요가 없었다..하나만 사용해도 되더라구요..

3. 요소갯수 count를 ++하고 0으로 리셋하는 부분 찾기

시작한 집에서 연결된 집의 개수를 DFS하면 count++

DFS가 끝났다면 count=0으로 리셋하고 house 리스트에 저장

나의 풀이

※코드에서 나만의 테스트용은 주석처리!!※

※결과물 출력은 테스트용 출력 및 백준 채점용 모두 출력한 결과물임!!※

시도1. 2-1 방법사용

: 방문한 흔적을 남기기 위해 방문여부 True False를 저장하는 visitied 리스트만 사용

시도2. 2-2 방법사용

: 2-1에서 사용한 별도의 visited 리스트 생성 없이 방문 했다면 바로 graph에서 1->0으로 바꿔줌

< 2-1, 2-2 방법 출력 결과 (결과 동일) >

결론

2-1방법이나 2-2방법이나 동일하다!

둘 중 편한것을 쓰면 되겠다

둘 중 하나를 이용하거나 둘 다 이용하는 답안 코드가 보이길래 모두 해보며 정리해보았다.