백준 2667: 단지번호 붙이기, 4963: 섬의 개수

문제

<2667: 단지번호 붙이기>

문제 링크: https://www.acmicpc.net/problem/2667

<4963: 섬의 개수>

문제 링크: https://www.acmicpc.net/problem/4963

위 두 문제는 해결하는데 있어 많이 유사하기 때문에 같이 포스팅을 하게되었습니다.

두 문제 전부 DFS 혹은 BFS를 사용하여 해결 할 수 있습니다.

저의 경우는 DFS 방법으로 문제를 해결하였습니다.

문제 푸는데 있어 핵심은 움직임에 있습니다. 

2667번의 경우, 상·하·좌·우로만 움직일 수 있습니다. 따라서 움직일 수 있는 방향을 먼저 지정을 해주어야 합니다.

4963번의 경우에는 상·하·좌·우 뿐만아니라 대각선까지 움직일 수 있습니다. 8개의 방향 모두 지정해주어야 합니다.

또, 중요한 것은 주어진 지도를 벗어나면 안된다는 것입니다. 범위를 주어 지도를 벗어나지 않도록 해주어야 합니다.

4963번의 경우, 실수할 수 있는 부분은 지도를 지정할 때나 움직일때, 행과 열을 잘 지정해주어야 합니다. 

2667번은 정사각형이기 때문에 모르고 넘어가도 상관이 없지만, 4963번의 지도는 행과 열이 다를 수 있기 때문에 잘 지정해 주어야 합니다.

이중 for문을 사용하였을 때, 순서가 중요하기때문에 이를 바꾸었을 시에 답이 이상하게 나올 수 있습니다.

저도 이부분에서 실수를 하여 조금 시간이 걸렸습니다;;;;

코드

<2667: 단지번호 붙이기>

#include <cstdio>
#include <algorithm>
using namespace std;
int a[30][30];
int d[30][30];
int dx[] = {0,0,1,-1};  //움직이는 방향
int dy[] = {1,-1,0,0};  //상,하,우,좌 순서
int n;
int ans[25*25];
void dfs(int x, int y, int cnt) {
    d[x][y] = cnt;
    //4방향으로 움직여야 하기 때문에 포문을 써서 함.
    for (int k=0; k<4; k++) {
        int nx = x+dx[k];
        int ny = y+dy[k];
        //움직였을 때, 범위를 벗어나면 안된다.(움직임은 맵 상에서만.)
        if (0 <= nx && nx < n && 0 <= ny && ny < n) {
            //맵에서 1로 표시되어있어야하며, 방문했던 곳인지 확인.
            if (a[nx][ny] == 1 && d[nx][ny] == 0) {
                dfs(nx, ny, cnt);
            }
        }
    }
}
int main() {
    scanf("%d",&n);
    //지도 입력 받기
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%1d",&a[i][j]);
        }
    }
    int cnt = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (a[i][j] == 1 && d[i][j] == 0) {
                dfs(i, j, ++cnt);
            }
        }
    }
    printf("%d\n",cnt);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            ans[d[i][j]]+=1;
        }
    }
    sort(ans+1, ans+cnt+1);
    for (int i=1; i<=cnt; i++) {
        printf("%d\n",ans[i]);
    }
    return 0;
}

<4963: 섬의 개수>

#include <iostream>
using namespace std;
 
int map[51][51];    //지도를 할당.
int isLand[51][51]; //땅인지 확인.
int dx[] = {-1,0,1,-1,1,-1,0,1};    //움직임 8방향(대각선 포함).
int dy[] = {1,1,1,0,0,-1,-1,-1};    //좌상, 상, 우상, 좌, 우, 좌하, 하, 우하
int w,h;
 
void dfs(int x, int y, int key){
    isLand[x][y]=1;
    for(int i=0; i<8; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(0<=nx && nx<h && 0<=ny && ny<w){
            if(map[nx][ny]==1 && isLand[nx][ny]==0){
                dfs(nx,ny,key);
            }
        }
    }
}
 
int main(){
    while(true)
    {
        cin >> w >> h;
        if(w==0 && h==0) break;
        
        //행과 열 순서 중요!!
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                cin >> map[i][j];
                isLand[i][j] = 0;
            }
        }
        int key=0;
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(map[i][j]==1 && isLand[i][j]==0){
                    dfs(i,j,++key);
                }
            }
        }
        cout << key<<"\n";
    }
    return 0;
}