글 읽기 - 큐와 스택을 사용하지 않았습니다.

sdf3265 5년 전 0

안녕하십니까

아래의 코드로 '맞았습니다' 결과를 얻었습니다.

헌데, 다른 이들의 코드를 보니 모두 스택이나 큐를 사용하셨더군요.

스택이나 큐를 사용하지 않고 아래와 같이 코딩하면 너무 원시적인 방법인 것인가요?

혹여 응용된 다른 문제를 풀지 못할까 염려하여 질문드립니다.

감사합니다.

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int a[100][100];
int d[100][100];
int dx[8] = { 0,0,-1,1,-1,1,1,-1 };
int dy[8] = { -1,1,0,0,-1,1,-1,1 };
void dfs(int x, int y) {
	d[x][y] = 1;
	for (int k = 0; k < 8; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];

		if (nx >= 0 && nx < 50 && ny >= 0 && ny < 50) {
			if (d[nx][ny] == 0 && a[nx][ny] == 1) {
				dfs(nx, ny);
			}
		}
	}

}
int main() {
	while (1) {
		int w = 0;
		int h = 0;
		cin >> w >> h;
		if (w == 0 && h == 0) {
			break;
		}
		memset(a, 0, sizeof(a));
		memset(d, 0, sizeof(d));

		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> a[i][j];
			}
		}
		int cnt = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (d[i][j] == 0 && a[i][j] == 1) {
					dfs(i, j);
					cnt = cnt + 1;
				}
			}
		}
		cout << cnt << endl;

	}
	return 0;
}

sdf3265 5년 전 0

그리고 질문이 하나 더 있습니다.

문제에 보면 w와 h는 50보다 작거나 같은 양의 정수이다. 라고 하는데 왜 a의 크기를 [100][100]으로 두어야 하는 것인지요?

[50][50] 으로 두어도 충분하지 않나요?

답변 주시면 큰 도움될 것입니다.

감사합니다

bupjae 5년 전 0

1. dfs 는 자기 자신을 재귀호출 하고 있습니다. 재귀호출을 쓸 때는 (직접 스택을 구현하지는 않더라도) 언어 구현체에서 제공하는 "호출 스택" 을 사용하는 것이라고 생각하셔야 합니다.

2. 이 코드는 배열 크기를 [50][50] 으로 할당해도 괜찮을 거라고 생각합니다. 필요 크기보다 조금 더 많이 할당하면 저지르기 쉬운 몇 가지 실수들 (예를들어 0~49 까지 써야 하는데 1~50을 쓴다든지...) 을 저지르더라도 프로그램이 올바르게 동작하게 합니다.

3. 이 답안지는 이 문제를 푸는 정석 풀이 중 하나입니다. 크게 걱정하지 않으셔도 됩니다.

sdf3265 5년 전 0

항상 고수님들의 답변에 큰 도움 얻고 있습니다.

정말 감사드립니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

큐와 스택을 사용하지 않았습니다.

sdf3265 5년 전 0

sdf3265 5년 전 0

bupjae 5년 전 0

sdf3265 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말