NumberOfIsland_DFS 강의 중

인프런 커뮤니티 질문&답변

정말 쉽게 풀어보는 코딩 테스트 top 기본 문제 (with 자바)

1) 섬의 수(NumberOfIsland)_DFS_문제설명

작성

145

32:00 분쯤에

System.out.println("result count grid[" + i + "][" + j + "] " + grid[i][j]);

로

result count grid[0][0] 1

result count grid[0][4] 1

result count grid[2][4] 1 이 좌표 3개를 확인하신건,

for문이 새로 돌게 될 때, 육지가 새로 시작(?) 되기 때문이 맞나요?

저 3개 좌표에서 각각 육지가 새로 시작(?) 되는게 맞죠?

답변 1

지식공유자

안녕하세요. 이해하신거 맞습니다.

이중 for문을 돌리면서 1을 처음으로 찾고( grid[0][0]) , 사방으로 돌려서 파고드는거죠.

값이 1인 것들을 다 찾아낸 후 빠져나오는 식입니다.

로그를 찍으면 이런식으로 되는거죠

i: 0 j 0

i: 1 j 0

i: 2 j 0

i: 2 j 1

i: 1 j 1

i: 0 j 1

i: 0 j 2

============

i: 0 j 4

============

i: 2 j 4

i: 3 j 4

============

이런식의 dfs 문제는 너무 응용이 다양합니다.

NumberOfIsland는 문제는 그냥 술술 외우셔야 합니다. 그래야 비슷한 문제를 응용이 가능합니다.

아울러 NumberOfIsland_bfs 유형도 너무 많이 나옵니다.

질문 감사드리며, 언제든지 궁금한거 올려주세요

화이팅~

작성한 질문수