섬나라 아일랜드
N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.
각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다.
섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
만약 위와 같다면 섬의 개수는 5개입니다.
입력 설명
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다.
두 번째 줄부터 격자판 정보가 주어진다.
출력 설명
첫 번째 줄에 섬의 개수를 출력한다.
입력
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
출력
5
틀린 구현 코드
public class 섬나라아일랜드 {
static int N;
static int[][] map;
static int answer = 0; //섬의 개수
static int[] dx = {0, 1, 0, -1};
static int[] dy = {1, 0, -1, 0};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt();
map = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = in.nextInt();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1) {
dfs(i, j);
}
}
}
System.out.println(answer);
}
static void dfs(int x, int y) {
map[x][y] = 0; //간 곳으로 마크
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx <= N - 1 && ny >= 0 && ny <= N - 1 && map[nx][ny] == 1) {
map[nx][ny] = 0; //간 곳으로 마크
}
}
boolean flag = false;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx <= N - 1 && ny >= 0 && ny <= N - 1 && map[nx][ny]==1){
flag = true;
break;
}
}
if (!flag) {
System.out.println(x+" "+y);
//사방이 다 0인 경우.
answer++;
}
}
//4방향으로 뻗었는데 주변이 다 0일 경우에 answer++
}DFS 구현 코드
public class 섬나라아일랜드 {
static int N;
static int[][] map;
static int answer = 0; //섬의 개수
static int[] dx = {-1,-1,0,1,1,1,0,-1};
static int[] dy = {0,1,1,1,0,-1,-1,-1};
//문제에서 상하좌우와 대각선이라고 명시
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt();
map = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = in.nextInt();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1) {
answer++;
map[i][j] = 0;
dfs(i,j);
}
}
}
System.out.println(answer);
}
static void dfs(int x, int y) {
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 1) {
map[nx][ny] = 0; //간 곳으로 마크
dfs(nx,ny);
}
}
}
}
이와 비슷한 유형인 이전 문제들에서 방향을 4방향으로 잡았어서인지 문제에서 상하좌우와 대각선이라고 명시했음에도 불구하고 4방향에 대해서 체크하는 식으로 구현했음.
원래 구현하고자 했던 것은
탐색하다 1인 지점에서 dfs.
주변 4방향을 보면서 1이면 0으로 바꾸고 주변이 모두 0인 경우에 answer++.
4방향인 것을 제외하고 말로만 풀면 얼추 맞는 생각 같은데 구현한 코드에는 문제가 있음.
문제점
1. 주변 방향을 돌면서 1일 경우에 0으로 바꿔주고 dfs호출하는게 아니라 방향 다돌고나서 주변을 한번 다시 돌면서 주변이 다 0일 경우 answer++하는 방식. 이러면 주위 방향을 제외한 이어진 섬들은 다른 섬으로 카운트 됨.
실제로 고치기 전 코드를 실행해보면 5보다 큰 수가 출력됨.
- 알고리즘
for문 돌면서 1인 지점에서 값 0으로 바꾸어주고 answer ++ , dfs 호출
8방향에 대해서 1인지 체크
-> 1일 경우 0으로 바꿔줌, dfs호출
+ BFS 구현 코드
public class 섬나라아일랜드_BFS {
static int N;
static int[][] map;
static int answer = 0; //섬의 개수
static int[] dx = {-1,-1,0,1,1,1,0,-1};
static int[] dy = {0,1,1,1,0,-1,-1,-1};
//문제에서 상하좌우와 대각선이라고 명시
static Queue<Point> queue = new LinkedList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt();
map = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = in.nextInt();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 1) {
answer++;
queue.add(new Point(i,j));
map[i][j] = 0;
bfs();
}
}
}
System.out.println(answer);
}
static void bfs() {
while(!queue.isEmpty()){
Point cp = queue.poll();
for (int i = 0; i < 8; i++) {
int nx = cp.x + dx[i];
int ny = cp.y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] == 1) {
map[nx][ny] = 0; //간 곳으로 마크
queue.add(new Point(nx,ny));
}
}
}
}
static class Point{
int x;
int y;
public Point(int x,int y){
this.x = x;
this.y = y;
}
}
}- 알고리즘
for문 돌면서 1인 지점에서 0으로 바꾸어주고 answer++,queue에 좌표 add후 bfs호출(호출시 좌표값 필요x)
queue가 비어있지 않으면 하나빼서 8방향 검사
1인 곳이 있으면 0으로 바꾸고 queue에 add
