문제 설명

• 지도에 있는 섬의 개수를 출력하는 문제
• 다른 그래프 문제와 다른 점의 대각선으로 이어진 섬도 하나의 섬으로 봐야한다는 점

문제 해결 Key_point

• 대각선까지 연결된 것으로 봐야하므로 방향을 나타내는 벡터를 조금 다르게 구성해야함
• 그리고 나머지는 dfs나 bfs 사용(이번에는 dfs를 사용)

문제 해결 아이디어

• vector<int> dx = {-1, -1, -1, 0, 1, 1, 1, 0}; //x축 이동 정의 (대각선까지 포함)
• vector<int> dy = {-1, 0, 1, 1, 1, 0, -1, -1}; //y축 이동 정의 (대각선까지 포함)
• 이런식으로 방향 벡터 구성
• 전역 변수 vector에 지도를 입력받고, get_count 함수 호출
• get_count에서 지도를 돌면서 섬을 찾음
  • 만약 섬을 찾는다면 dfs를 통해 연결된 섬을 찾음(그걸 하나의 섬으로 생각하여 나머지도 방문처리)
  • 연결된 섬 하나당 count 1 증가
• 마지막에 Count 반환하여 결과 출력
• 0 0 이 입력되면 반복 끝

소스 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> dx = {-1, -1, -1, 0, 1, 1, 1, 0}; //x축 이동 정의 (대각선까지 포함)
vector<int> dy = {-1, 0, 1, 1, 1, 0, -1, -1}; //y축 이동 정의 (대각선까지 포함)

vector<vector<int>> map;
vector<vector<bool>> visited;
int width = -1, height = -1;

void dfs(int x, int y) { //dfs 함수
    visited[x][y] = true; //현재 지점 방문 처리

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

        if (nx >= 0 && nx < height && ny >= 0 && ny < width) { //지도 안에 있으며
            if (map[nx][ny] == 1 && !visited[nx][ny]) { //방문되지 않은 섬인 경우 dfs 재귀로 탐색
                dfs(nx, ny);
            }
        }
    }
}

int get_count() { //지도에 있는 총 섬의 개수 count
    int count = 0;
    visited.assign(height, vector<bool>(width, false)); //방문 배열 초기화

    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (map[i][j] == 1 && !visited[i][j]) { //땅이면서 방문되지 않은 것을 찾음
                dfs(i, j); //찾았다면 dfs로 주변에 연결되어 있는 섬들을 찾음(이건 하나로 처리할거임)
                count++; //그리고 1 증가
            }
        }
    }
    return count; //다 찾으면 count 반환
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    while (true) {
        cin >> width >> height;
        if (width == 0 && height == 0) break;
        map.assign(height, vector<int>(width));

        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                cin >> map[i][j];
            }
        }

        cout << get_count() << endl;
    }

    return 0;
}

소감

처음에 대각선 조건을 못보고 dx dy를 가로 세로만 생각해서 틀렸다. 그리고 while 반복문 중에서 종료 조건을 while(여기) 넣었어서 입력을 받고 한번 출력한 다음에 종료되어 틀렸었다. 다음부터는 문제를 조금 더 자세히 읽어야겠다.