문제 : 섬나라 아일랜드(DFS 활용)
문제 설명
N*N 의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0
만약 위와 같다면
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.
두 번째 줄부터 격자판 정보가 주어진다.
▣ 출력설명
첫 번째 줄에 섬의 개수를 출력한다.
▣ 입력예제 1
7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0
내코드
function solution(board) {
let answer = 0; // 섬 갯수
// 좌표기준 이동가능한 방향을 모두 저장해둔 배열 moveArr
let moveArr = [
[-1, -1], // 좌측 상단 방향
[-1, 0], // 상단 방향향
[0, -1], // 촤측 방
[-1, 1], // 우측 상단 방향
[0, 1], // 우측 방향
[1, -1], // 좌측 하단 방향
[1, 0], // 하단 방향
[1, 1], // 우측 하단 방향
];
// 연결된 섬이 있는지 확인을 위한 재귀 함수 DFS 선언
function DFS(y, x) {
board[y][x] = 0; // 방문여부 확인을 위해 현재 좌표의 값을 0 으로 초기화
// 이동할 수 있는 좌표를 전부 확인하기 위해 반복
for (const [moveY, moveX] of moveArr) {
const Y = y + moveY; // 이동할 y 좌표 위치를 나타낼 변수 Y 선언
const X = x + moveX; // 이동할 x 좌표 위치를 나타낼 변수 X 선언
// Y, X 값이 0 이상 board.length 미만인 경우 즉 이동할 수 있는 좌표만 확인
if (Y >= 0 && Y < board.length && X >= 0 && X < board.length) {
// 이동할 좌표에이어진 섬이 있는 경우 이동한 위치좌표를 기준으로 추가 탐색을 위해 함수를 재귀적으로 호출
if (board[Y][X] === 1) {
console.log(`이어진 섬 발견! 좌표: [${Y},${X}]`);
DFS(Y, X);
}
}
}
}
// 2중 for 문으로 전체 배열 순회
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board.length; j++) {
// 현재 좌표에 섬이 있다면 현재 좌표로 DFS 함수 호출
if (board[i][j] === 1) {
answer++; // 섬 발견했으므로 answer 1 증가
console.log(`새로운 섬탐색 시작! 좌표: [${i},${j}]`);
DFS(i, j);
console.log("------- 섬탐색 종료 -------");
}
}
}
return answer;
}
let arr = [
[1, 1, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0],
[1, 0, 1, 0, 1, 0, 0],
];
console.log(solution(arr));
풀이
- 좌표 기준 이동 가능한 방향을 모두 저장해둔 2차원 배열
moveArr
선언 - 연결된 섬이 있는지 확인을 위해 현재 좌표 값
y
,x
를 인자로 가지는 재귀 함수DFS
선언- 함수 안에서 방문 여부 확인을 위해 현재 좌표의 값을 0 으로 초기화하고
moveArr
를 반복하면서 이동할 수 있는 좌표를 전부 확인 - 만약 이동할 좌표에 이어진 섬이 있는 경우 이동한 위치 좌표를 기준으로 추가 탐색을 위해 함수
DFS
를 재귀적으로 호출
- 함수 안에서 방문 여부 확인을 위해 현재 좌표의 값을 0 으로 초기화하고
- 2중
for
문으로 배열 순회하며 좌표에 섬이 있다면 현재 좌표로DFS
함수 호출
보완할 수 있는 부분
// 기존코드
let moveArr = [
[-1, -1], // 좌측 상단 방향
[-1, 0], // 상단 방향향
[0, -1], // 촤측 방
[-1, 1], // 우측 상단 방향
[0, 1], // 우측 방향
[1, -1], // 좌측 하단 방향
[1, 0], // 하단 방향
[1, 1], // 우측 하단 방향
];
...
for (const [moveY, moveX] of moveArr) {
const Y = y + moveY;
const X = x + moveX;
...
}
// 보완코드
let dx=[-1, -1, 0, 1, 1, 1, 0, -1];
let dy=[0, 1, 1, 1, 0, -1, -1, -1];
...
for(let k=0; k<8; k++){
let nx=x+dx[k];
let ny=y+dy[k];
...
}
코드 컨벤션 때문에 2차원 배열 선언 부분이 길어질 수 있으므로 배열 두개로 선언해 선언 부분을 2줄로 줄일 수 있음
참고
'코딩 테스트 문제 및 풀이' 카테고리의 다른 글
[JS] 코딩 테스트 문제 : 동전 교환 [배낭(KnapSack) 알고리즘] (0) | 2024.05.29 |
---|---|
[JS] 코딩 테스트 문제 : 계단오르기 [동적계획] (0) | 2024.05.22 |
[JS] 코딩 테스트 문제 : 송아지 찾기 [BFS : 상태트리탐색] (0) | 2024.04.23 |
[JS] 코딩 테스트 문제 : 이진트리 넓이 우선 탐색 [BFS] (0) | 2024.04.05 |
[JS] 코딩 테스트 문제 : 미로탐색 [DFS] (0) | 2024.04.02 |