백준 2667번 문제풀이
방문하지 않은 곳에서 dfs를 호출한다?
dfs는 결국 나와 이어진 노드를 재귀로 탐색하는 그래프 탐색 알고리즘이다.
맵에서 단지수를 어떻게 세야 할까? - 미방문한 집을 발견하면 단지가 아닌 집임. 이 집을 dfs 입력값으로 넣어 단지의 가구 수를 반환한다.
7X7의 map을 우선 입력값으로 받는다.
dfs 탐색을 어디서부터 어떻게 해나가야 할까? - [0][0]
이 문제도 역시 visited 리스트를 활용해야 할까? - 그렇다
배열순회에서 dfs호출 과정이 이해가 안됐다.
검사 조건에 4 방향 검사하고 통과시, 4방향 노드를 큐에 넣고 탐색하면 된다는데
솔직히 아직 어렵다.
풀이영상을 보면서 이해해보자.
1. 배열을 순회 - 미방문 집 - 해당 집에서 bfs/dfs 시작 - bfs/dfs는 단지의 개수를 반환
2. 반환된 개수를 정답 리스트에 저장. 이후 정렬하고 len(정답), *정답 으로 출력
bfs 탐색에서 연결된 집을 검사하는 방법이 헷갈렸음.
해당 문제의 bfs 구현
def bfs(si, sj):
q = []
q.append((si,sj))
visited[si][sj] = 1
cnt = 1
while q:
ci, cj = q.pop(0)
for di,dj in ((-1,0),(1,0),(0,1),(0,-1)):
ni,nj = ci+di, cj+dj
if 0<=ni<=N and 0<=nj<=N and arr[ni][nj] == 1 and v[ni][nj] == 0:
q.append((ni,nj))
v[ni][nj] = 1
cnt += 1
return cnt아 [i][j]를 큐에 같이 넣는다. 그러니까 node에 하나만 들어가는게 아님.
큐를 팝해서 문제 조건을 추가한다. 상하좌우의 모든 노드를 bfs로 탐색하는 과정을 추가한다.
이 조건을 만족하면서 + arr = 1 + v = 0 미방문 + 섬 발견시 bfs를 재귀로 호출.
그리고 cnt를 1개 늘린다. (단지에 섬의 개수를 센다.)
dfs로 풀어볼 엄두도 안 난다. 솔직히 다시 풀래도 못 풀 거 같다. 이대로 솔브하는 건 아닌 것 같아서 쉬운 유형 풀어보고 다시 도전하겠다.
리스트원소 줄 바꾸면서 출력
*arr, sep='\n'
