백준 4963번: 섬의 개수 with Java

섬의 개수 다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

72864

37096

26591

49.681%

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

예제 입력 1 복사

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

예제 출력 1 복사

0
1
1
3
1
9

 

 

---

 

진짜 뭐라는 걸까/ 섬의 개수 ? 아 진짜 모르겟는데욥? 한 정사각형과 가로, 세로, 대각선.... 아니 진짜로 이렇게 이해할 수 없는 문제는 처음이얍.... 그냥. 걍. 이해가 안 돼 뭔 소리임? 잠깐 누워야겠음

 

뭘 ... 구하는 거지.... 섬의 개수..... ㅇㅎ........ 

?

모르겟오

 

결국 지피티한테 문제 해석 부탁함;;; 

->

물론입니다! 이 문제는 "섬의 개수"를 세는 문제인데, 쉽게 설명해볼게요.

문제의 개념

1. 지도: 문제에서는 정사각형으로 이루어진 지도가 주어져요. 이 지도는 바다(0)와 땅(1)으로 이루어져 있어요.
2. 섬: 땅(1)들이 모여서 하나의 덩어리를 이루면, 그 덩어리가 '섬'이 돼요. 섬은 땅이 가로, 세로, 대각선으로 연결되어 있으면 하나의 섬으로 봅니다.
3. 목표: 지도에서 몇 개의 '섬'이 있는지 세는 거예요.

예시로 이해해보자

예를 들어, 아래와 같은 지도가 있다고 해볼게요:

코드 복사

1 0 1 0 1 0 1 0 1

여기서, 숫자 1은 땅, 숫자 0은 바다를 의미해요.

• 1번 섬: 첫 번째 줄의 1 (왼쪽 위)
• 2번 섬: 첫 번째 줄의 1 (오른쪽)
• 3번 섬: 두 번째 줄의 1 (가운데)
• 4번 섬: 세 번째 줄의 1 (왼쪽 아래)
• 5번 섬: 세 번째 줄의 1 (오른쪽 아래)

이 지도의 경우, 총 5개의 섬이 있어요. 각 섬은 다른 땅들과 연결되어 있지 않아서, 따로따로 섬으로 세어야 해요.

문제 해결 방법

이 문제를 해결하려면, 지도의 모든 땅(1)을 하나씩 확인하면서 이 땅이 새로운 섬의 일부인지 알아보면 돼요.

1. 땅을 찾기: 지도를 차례대로 확인하다가 땅(1)을 찾으면, 그 땅에서 시작해 연결된 모든 땅을 확인해요.
2. 연결된 땅 찾기: 만약 연결된 다른 땅(1)이 있으면, 그 땅도 같은 섬에 속해요. 이렇게 연결된 모든 땅을 다 확인하면 하나의 섬을 찾은 거예요.
3. 섬 개수 세기: 새로운 섬을 찾을 때마다 섬 개수를 1씩 증가시키면 돼요.

정리

이 문제는 지도의 각 땅(1)이 다른 땅들과 어떻게 연결되어 있는지를 찾는 문제에요. 땅들이 모여서 몇 개의 독립된 섬을 이루고 있는지를 세는 게 목표랍니다.

이제 이해가 좀 되었나요? 어렵게 느껴질 수 있지만, 핵심은 "연결된 땅들이 모여 하나의 섬을 이룬다"는 개념이에요.

 

 

지피티............ 니가 나보다 낫다야.......................;; 코테 볼 때 지피티 데려가게 해주세요 지피티는 제 친구이자 영혼입니다 예예..... 

이해 완.

1이 섬이고 가로세로대각선으로 연결되어 있으면 섬 1개로 친다는 말씀이시쥬? 저 예시 이미지는 그러면 섬 3개....!!!!  오께

 

생각을 해보자. 와 근데 대각선까지... 세야 한다니 2차원 배열로 해서 가로세로 1 더해보고 대각선까지 체크해보고 아.. 방문한 곳은 체크를 해봐야하나?? 오 이거 깊이...깊이.... 깊이..... DFS......... 무슨 약자더라? 깊이우선탐색? FS는 뭔 단언지 기억 안 남 일단 패스

 

일단 해보도록 하자 

 

와 생각보다 빡셌다. 그.... 하나의 1이 있으면 확인해야 할 곳이... 8곳이나 된다!!!!!!!! 죄송한데 저 방향 배열은 참고를 좀 했습니다 너무 헷갈려서요 하하하하하하하하하 이러면 안 되는데...

암튼 저 배열 친구는요 0 1 / 0 - 1 이런 식으로 오른쪽 왼쪽 그 확인해야 할 8개 지점을 하나씩 탐색하는 친구들이랍니다... 참 착한 친구들이에요

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BJ_4963 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String whString;
		while (!(whString = br.readLine()).equals("0 0")) {
            String[] wh = whString.split(" ");
            int w = Integer.parseInt(wh[0]);
            int h = Integer.parseInt(wh[1]);
            
            int[][] map = new int[h][w];
            boolean[][] visited = new boolean[h][w];

            // 지도 입력 받기
            for (int i = 0; i < h; i++) {
                String[] row = br.readLine().split(" ");
                for (int j = 0; j < w; j++) {
                    map[i][j] = Integer.parseInt(row[j]);
                }
            }
            
            int count = 0;

            // 모든 지점에 대해 섬 찾기
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (map[i][j] == 1 && !visited[i][j]) {
                        dfs(map, visited, i, j, h, w);
                        count++;
                    }
                }
            }

            System.out.println(count);
		}
	}
	
    // DFS 
    private static void dfs(int[][] map, boolean[][] visited, int x, int y, int h, int w) {
        // 방문했으니까 true 저장
        visited[x][y] = true;

        // 방향 배열 (상하좌우, 대각선 총 8방향)
        int[] dx = {0, 0, 1, -1, 1, 1, -1, -1};
        int[] dy = {1, -1, 0, 0, 1, -1, 1, -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 (map[nx][ny] == 1 && !visited[nx][ny]) {
                    dfs(map, visited, nx, ny, h, w);
                }
            }
        }
    }
}

 

 

 

 

맞았습ㄴ디ㅏ!!! 문제 해석이 진짜 빡셌다 .... 괜히 해석이 80이라고 하는 게 아님.

아

8월 25일 실화냐?

내 방학 

돌려줘요

제발

7월 25일이라고 해줘 살려줘...