섹션 8. DFS, BFS 활용 13. 섬나라 아일랜드(DFS)

문제

• N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.
• 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.
• 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.

• 만약 위와 같다면 섬의 개수는 5개입니다.

입력

• 첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.
• 두 번째 줄부터 격자판 정보가 주어진다.

출력

• 첫 번째 줄에 섬의 개수를 출력한다.

입출력 예제

---

풀이방식

이번 문제는 DFS에 대한 문제이다.

---

설계과정

1. 이동 방향을 담은 배열 dy, dx에 값을 넣어서 저장한다.

2. 큐를 선언하고, 큐에 미리 선언한 Point 객체 값을 넣는다.

3. 출발점은 무조건 방문하므로 1을 넣는다.

4. 경계선 안쪽이고 통로라면 지나갈 수 있는 곳이므로 board 배열에 1을 넣어서 방문기록을 남긴다.

5. 큐에 현재 좌표 값을 넣고 dis 배열에 좌표값에 1을 더한 값을 넣는다.

6. 통로 끝까지 왔을 때에 값이 0이라면 -1을 출력하고, 아니라면 해당 값을 출력한다.

---

풀이과정

1. 각 변수들을 선언한다.

• 행의 이동 좌표를 위한 배열 dx[ ] 을 선언한다.
• 열의 이동 좌표를 위한 배열 dy[ ] 을 선언한다.
• 입력 기록을 저장할 배열 arr[ ] 을 선언한다.
• 현재 좌표에서 이동할 수 있는 방향을 알기 위해 nx, ny를 선언해서 dx[ ], dy[ ] 배열의 값을 각각 더해준다.
• 섬의 개수를 저장할 result 을 선언한다.

2. solution 메소드를 작성한다.

• 섬을 만날 때마다 호출하는 메소드로, 섬의 개수를 파악한다.

3. 이중 for문 에서 board[i][j] 가 1이라면 result에 1을 누적하고, 0으로 값을 변경한 다음 DFS()를 호출한다.

• boar[i][j] 가 1이라는 것은, 육지라는 의미이다. 이는 즉 DFS의 시작점이라고도 할 수 있다.
• 출발점을 찾은 후에 값을 0으로 변경한다.
• 이 때, 출발점을 찾았다는 것은 섬의 시작을 의미하므로 result에 1씩 누적한다.
• DFS(i, j, board) 로 파라미터를 넣어서 재귀함수를 호출한다. 이 때 i, j는 처음 발견된 섬의 위치를 의미한다.

4. DFS 메소드를 작성한다.

• 8방향을 탐색하다가 더 이상 갈 곳이 없으면 종료한다.

5. 좌표 안에 영역이고, 좌표의 값이 1이라면 해당 좌표에 값을 0으로 바꿔주고 재귀함수를 호출한다.

• 모든 영역에서 1이 없어질 때 까지 수행한다.

6. 모두 수행했으면 result 를 출력한다.

---

더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.