[백준/C++]#4963 - 섬의 개수

풀이

#include <iostream>
using namespace std;

int a[51][51];
bool ck[51][51];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};		//상하좌우 대각
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int w,h;

void dfs(int y, int x, int CNT) {
	ck[y][x] = true;
	for (int k=0; k<8; k++) {	// 상하좌우 대각 이동
		int wx = x + dx[k];
		int hy = y + dy[k];
		if (0 <= wx && wx < w && 0 <= hy && hy < h) {
			if (a[hy][wx]==1 && ck[hy][wx]==false) {
				dfs(hy, wx, CNT);
			}
		}
	}
}

int main() {
	while (cin >> w >> h && (w!=0 && h!=0)) {	// w와 h가 모두 0이면 종료
		for (int i=0; i<h; i++) {
			for (int j=0; j<w; j++) {
				cin >> a[i][j];		// 입력
				ck[i][j] = false;	// ck 배열 초기화
			}
		}
		int cnt=0;
		for (int i=0; i<h; i++) {
			for (int j=0; j<w; j++) {
				if (a[i][j]==1 && ck[i][j]==false) {
					dfs(i, j, ++cnt);
				}
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}

개념

이렇게 입력의 개수 (테스트 케이스)가 주어지지 않는 문제는 입력을 EOF(End Of File)까지 받는다.

cin도 true 값을 반환하는 것에 착안하여 이를 반복문에 넣으면 된다.

 

문제의 경우 w, h가 0일 때 다른 값을 반환하지 않으므로 이를 종료 조건으로 만든다.

---

풀이

 

이전 문제를 생각하면 어렵지 않게 해결할 수 있다.

이번엔 상하좌우뿐 아니라 대각선 dfs 이동도 가능하다.

따라서 dx, dy 배열을 8방향으로 구성한다.

 

신경써야할 부분은, 여러번의 test case를 가지므로 ck 배열을 초기화해야한다는 것이다.

문제에서 가장 어려웠던 부분은 W와 H에 있었다.

너비와 높이가 주어지는데, 일반적인 순서인 (x, y)로 주어진다.

하지만 이차원 배열은 [y][x] 의 순서를 가진다.

 

이를 바탕으로 입력받을 때, for 문을 반복 할 때 주의해야한다.

또한 dfs 함수에서도 w와 h, x와 y의 관계를 생각하여 접근해야한다.

 

dfs 맨 앞에 cout << x << y << " "; 를 넣어서 오류에 접근했는데, 대부분의 오류는 행과 열을 거꾸로 참조하기 때문에 발생했다.

 

---

+a

 

다른풀이(from 백준github)

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int a[100][100];
int d[100][100];
int dx[] = {0,0,1,-1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,1,-1};
int n,m;
void bfs(int x, int y, int cnt) {
    queue<pair<int,int>> q;
    q.push(make_pair(x,y));
    d[x][y] = cnt;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        for (int k=0; k<8; k++) {
            int nx = x+dx[k];
            int ny = y+dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (a[nx][ny] == 1 && d[nx][ny] == 0) {
                    q.push(make_pair(nx,ny));
                    d[nx][ny] = cnt;
                }
            }
        }
    }
}
int main() {
    while (true) {
        scanf("%d %d",&m,&n);
        if (n == 0 && m == 0) break;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                scanf("%1d",&a[i][j]);
                d[i][j] = 0;
            }
        }
        int cnt = 0;
        for (int i=0; i<n; i++) {
            for (int j=0; j<m; j++) {
                if (a[i][j] == 1 && d[i][j] == 0) {
                    bfs(i, j, ++cnt);
                }
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

큐를 사용해 반복문으로 된 풀이이다.

EOF를 처리한 방식이 인상적인데, while문에 true를 넣고 break 문을 사용했다.