(코딩테스트) 백준_4963_섬의 개수 회고

 

문제

 

 

내가 최초 제출 답안 (틀림) 

public class testMain {

	static int[][] map ;
	static boolean[][] visted ;
	static int w ;
	static int h ;
	static int[] x = {-1,1,0,0} ; //높이
	static int[] y = {0,0,-1,1} ; //너비
	static int count =0 ;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//bfs 큐에 담아서 예약 걸어둠     , visied 영역 표시 잘해야함  함수 초기 코드 + 상하좌우 검증 코드에도 조건 부합시 que로 while 루프 돌림 
		//dfs 재귀로 끝까지 보냄. 
		// 둘다 상하좌우 변수 선언 + map + visted + count 필요  
		Scanner  sc = new Scanner(System.in);
		 w = sc.nextInt();
		 h = sc.nextInt();
		map = new int[h][w];
		visted = new boolean[h][w];
		
		//지도 채우기
		for(int i=0; i<h; i++) {
			for(int j=0;j<w; j++) {
				map[i][j]=sc.nextInt();				
			}
		}
		for(int i=0; i<h; i++) {			
			for(int j=0;j<w; j++) {
				if(!visted[h][w]) bfs(0,0); // 방문한적 없어? 그럼 bfs 시작				
			}
		}
	
		System.out.println(count); // 마지막에 카운트 출력 
	}
	
	public static void bfs(int h , int w ) {
		Queue<int[]> q = new LinkedList<>();
		visted[h][w] = true;
		int [] first = {h,w};
		q.offer(first);	

		while(!q.isEmpty()) {  //q 체킹
			int[] que= q.poll();
			int nh = que[0] , nw = que[1];
         	if(map[nh][nw]==1) count++; 		//  현재 위치 섬이야?
			int nextH ;   //다음 탐색할 높이?
			int nextW ;   //다음 탐색할 너비?
			for(int i =0 ; i<4;i++) {  // 상하좌우 탐색 고고
				 nextH = nh + x[i];
				 nextW = nw + y[i];
				 if(nextH > 0 && nextW > 0 && nextH < h &&  nextW < w) {  //범위내인지 체크 					 					 
					 if(!visted[h][w] ) { // 방문한적 없고 , 섬인지 체크
						 visted[h][w] = true;
						 int[] next = {nextH,nextW};
						 q.offer(next);
					 if(map[nextH][nextW]==1) {
						 count ++;
					 } 						 
					 }	 
				 }
				 	 
			}
			
			
		};
		
		
	}

}

 우선 문제 요약 (4963번)

• 1은 땅, 0은 바다.
• 상하좌우 + 대각선까지 포함하여 연결된 1들은 하나의 "섬"으로 간주.
• 여러 테스트 케이스가 주어지며, 각 테스트 케이스마다 섬의 개수를 출력해야 함.
• 입력 종료 조건: w h = 0 0

---

나의 코드 흐름 요약

• map, visited, bfs()를 활용해 섬을 셈.
• x, y 배열로 상하좌우 4방향을 탐색.
• BFS를 돌면서 섬이면 count++ 증가.

 

❌ 문제점 및 오류

1.  입력을 한 번만 받고, 여러 테스트 케이스를 고려하지 않음

• 문제는 여러 테스트 케이스가 주어짐.
• 현재는 w, h를 한 번만 받고 종료됨.

🔧 해결법: while (true) 루프 안에서 w == 0 && h == 0이면 종료하도록 해야 함.

---

2.  탐색 방향이 4방향밖에 없음

• 문제는 **8방향(상하좌우 + 대각선)**을 봐야 함.

🔧 dx, dy를 8방향으로 바꿔야 함:

int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

---

3.  if (!visited[h][w]) bfs(0,0) 라인이 잘못됨

• 무조건 (0,0)부터 BFS 시작하고 있음.
• 그리고 조건도 visited[h][w]인데, h와 w는 맵 크기라서 인덱스 범위 초과 오류가 발생함.

🔧 수정:

if (!visited[i][j] && map[i][j] == 1) {
    bfs(i, j);
    count++;
}

---

4.  BFS 내에서 섬을 만날 때마다 count++함

• 섬 개수는 BFS 하나당 1개만 세야지, BFS 내부에서 count++하면 섬 내부에서 여러 번 셈.

🔧 해결: count++는 BFS 외부에서 한 번만 해야 함. 내부에서 하면 X

---

5.  방문 체크가 잘못된 좌표로 되어 있음

if (!visited[h][w]) ...

• 여기도 nextH, nextW 써야 함. h, w는 처음 시작 좌표

🔧 수정:

if (!visited[nextH][nextW] && map[nextH][nextW] == 1) {
    visited[nextH][nextW] = true;
    q.offer(new int[]{nextH, nextW});
}

 

 

 

 

 

개선된 코드 

 

import java.util.*;

public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int w, h;

    // 8방향: 상하좌우 + 대각선
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            w = sc.nextInt();
            h = sc.nextInt();

            if (w == 0 && h == 0) break;

            map = new int[h][w];
            visited = new boolean[h][w];

            // 지도 입력
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    map[i][j] = sc.nextInt();
                }
            }

            int count = 0;

            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (!visited[i][j] && map[i][j] == 1) {
                        bfs(i, j);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }

        sc.close();
    }

    public static void bfs(int startX, int startY) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{startX, startY});
        visited[startX][startY] = true;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int x = current[0];
            int y = current[1];

            for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
                    if (!visited[nx][ny] && map[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

 

 

 

 

 

최종 회고.

1. 상하좌우 뿐만 아니라 , 대각선까지 고려하지 못함. (문제 파악X ) + 연결된 섬을 하나인걸 인지 못했음.

2. Scanner 대신 ->  BufferedReader 습관화

  

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());