[백준 C++ 4936번] 섬의 개수

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

---

이해하기 

유기농배추(https://xoxoxoxox.tistory.com/118), 단지 번호 붙이기 문제(https://xoxoxoxox.tistory.com/125)와 유사했던 문제였다. 

이 문제의 특이점은 대각선에 있는 것도 연결된 걸로 본다는 것이었다. 

또, 테스트 케이스가 여러 개 주어져 while문으로 반복해서 입력을 받아야 했고, 매번 map[][]과 visited[][]를 초기화 시켜줘야 했다. 

 

대각선에 있는 것도 연결된 거에 포함 시키기

int xpos[8] = {-1, 1, 0, 0, -1, -1, 1, 1}; 
int ypos[8] = {0, 0, 1, -1, 1, -1, 1, -1};

 

뒤에 4개는 상하좌우의 대각선 좌표를 추가해준 것이다. 

 

문제점 1 : 정사각형이 아니므로 map[y][x]로 y와 x의 순서를 바꿔서 호출해줘야 함

void dfs(int y, int x){
    visited[y][x] = 1;
    
    for(int i=0; i<8; i++){
        int nxpos = x + xpos[i];
        int nypos = y + ypos[i];
        
        if( nxpos < 1 || nxpos > w || nypos < 1 || nypos > h) continue;
        if(visited[nypos][nxpos]==0 && map[nypos][nxpos]==1) dfs(nypos, nxpos);
    }
    
}

 

---

최종 코드

#include <iostream>
using namespace std;

int map[51][51]={0,};
int visited[51][51] = {0,};
int xpos[8] = {-1, 1, 0, 0, -1, -1, 1, 1}; 
int ypos[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int w, h;
int cnt;

void dfs(int y, int x){
    visited[y][x] = 1;
    
    for(int i=0; i<8; i++){
        int nxpos = x + xpos[i];
        int nypos = y + ypos[i];
        
        if( nxpos < 1 || nxpos > w || nypos < 1 || nypos > h) continue;
        if(visited[nypos][nxpos]==0 && map[nypos][nxpos]==1) dfs(nypos, nxpos);
    }
    
}

int main()
{
    while(1){
        cin >> w >> h;
        //0 0이 나오면 테스트 케이스 끝끝
        if(w==0 && h==0) break;
        
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++) {
                cin >> map[i][j];
            }
        }
        
        cnt=0;
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++){
                if(map[i][j] == 1 && visited[i][j] == 0) {
                    cnt++;
                    dfs(i,j);
                }
            }
        }
        
        cout << cnt << "\n";
        
        //0으로 다시 초기화화
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++) {
                map[i][j]=0;
                visited[i][j]=0;
            }
        }
    }
    
    return 0;
}