글 읽기 - DFS 스택 오버플로우 문제 질문드립니다.

quffl9612 5년 전 0

혼자 생각한 방법으로 풀었던 문제를 세련된 방법으로 다시 풀어보고 있는데요....

컴파일은 되는데, dfs 함수 인자에 접근이 안됩니다.... ㅠㅠ

제 배경지식으로는 왜 스택 오버플로우가 나는지 도저히 이해가 안돼서 열심히 검색을 해봐도 모르겠네요 ㅠ

도움 부탁드립니다 ㅠㅠ

PS : safe 함수는 원래 dfs 함수 안에서 조건문으로 처리했었는데, 이것저것 해보다가 혹시하고 만들었습니다.

추가하기 전에는 dfs 인자 접근이 안됐는데, safe함수를 넣고 나서는 safe 함수 인자에 접근할 때 스택 오버플로우가 납니다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
int n, map[25][25], size[625], count = 1;
int dx[4] = { -1, 1, 0, 0};
int dy[4] = { 0, 0, 1, -1};

int safe(int a, int b) {
	return (0 <= a && a < n) && (0 <= b && b < n);
}

void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void input() {
	scanf("%d", &n);
	char temp[26];
	for (int i = 0; i < n; i++) {
		scanf("%s", temp);
		for (int j = 0; j < n; j++)	{
			map[i][j] = temp[j] - '0';
		}
	}
}

void dfs(int row, int col, int* c) {
	for (int a = 0; a < 4; a++) {
		if (safe(row + dx[a], col + dy[a]) == 1) {
			map[row][col] = *c;
			dfs(row + dx[a], col + dy[a], &c);
		}
	}
}

void sort() {
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < n; j++) {
			if (map[i][j]) size[count - 2]++;
		}
	}
	int min = -999;
	for (int i = 0; i < count - 1; i++) {
		int index = i;
		for (int j = i; j < count - 1; j++)	{
			if (min > size[j]) {
				min = size[j];
				index = j;
			}
			swap(&size[i], &size[index]);
		}
	}
}

int main() {
	input();
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1) {
				count++;
				dfs(i, j, &count);
			}
		}
	}
	sort();
	printf("%d\n", count - 1);
	for (int i = 0; i < count - 1; i++)	{
		printf("%d\n", size[i]);
	}
	system("pause");
	return 0;
}

luniro 5년 전 1

방문체크는 안하시나요?

quffl9612 5년 전 0

와.... 그냥 제가 알고리즘을 잘못짰네요... ㅎㅎ main함수에서 dfs 접근할때 방문처리 했다고 혼자 착각하고 있었어요.... 감사합니다 ㅠㅠ

quffl9612 5년 전 0

수정 했는데,여전히 safe 함수 인자 접근할 수 없다고 뜨네요 ㅠㅠ

void dfs(int row, int col, int c) {
	for (int a = 0; a < 4; a++) {
		if (map[row + dx[a]][col + dx[a]] == 1 && safe(row + dx[a], col + dy[a])) {
			map[row][col] = c;
			dfs(row + dx[a], col + dy[a], c);
		}
	}
}

quffl9612 5년 전 0

함수 인자를 지역변수로 받아서 넣으니 제대로 들어가네요...

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
int n, map[25][25], size[625], count = 1;
int dx[4] = { -1, 1, 0, 0};
int dy[4] = { 0, 0, 1, -1};

int safe(int a, int b) {
	return (0 <= a && a < n && 0 <= b && b < n);
}

void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void input() {
	scanf("%d", &n);
	char temp[26];
	for (int i = 0; i < n; i++) {
		scanf("%s", temp);
		for (int j = 0; j < n; j++)	{
			map[i][j] = temp[j] - '0';
		}
	}
}

void dfs(int row, int col, int c) {
	map[row][col] = c;
	for (int a = 0; a < 4; a++) {
		int x = row + dx[a], y = col + dy[a];
		if (map[x][y] == 1 && x >= 0 && x < n && y >= 0 && y < n) {
			dfs(x, y, c);
			map[x][y] = c;
		}
	}
}

void sort() {
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < n; j++) {
			if (map[i][j]) size[map[i][j] - 2]++;
		}
	}
	
	for (int i = 0; i < count - 1; i++) {
		int index = i, min = 999;
		for (int j = i; j < count - 1; j++)	{
			if (min > size[j]) { min = size[j]; index = j;
			}
		}
		swap(&size[i], &size[index]);
	}
}

int main() {
	input();
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1) {
				count++;
				dfs(i, j, count);
			}
		}
	}
	sort();
	printf("%d\n", count - 1);
	for (int i = 0; i < count - 1; i++)	{
		printf("%d\n", size[i]);
	}
	return 0;
}

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

문제

문제

출처

ICPC

DFS 스택 오버플로우 문제 질문드립니다.

quffl9612 5년 전 0

luniro 5년 전 1

quffl9612 5년 전 0

quffl9612 5년 전 0

quffl9612 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말