[백준 C]4963 섬의 개수

DFS, BFS 개념 : https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

1. map[][] 을 한번 만들고 수정할 필요가 없다. -> 수정을 해야한다면 (insert, delete) linkedList 로 연결해주어야겠지?

2. 이어진 섬(1)들 뭉탱이를 찾아야 한다. -> 섬을 발견했을 때 이어진 섬을 찾아야 한다. dir을 이용해 이어진 섬 찾자.

3. 이미 간 섬들을 표시해야한다. -> 섬 노드에 data 넣는게 더 귀찮으니 visited[][]을 만들자.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*##### DFS,BFS https://devuna.tistory.com/32 #####*/

#define MAX_SIZE 60

int map[MAX_SIZE][MAX_SIZE]; // int **map 으로 나중에 동적할당을 해주려면 scanf 로 입력받은 숫자들을 하나하나 슬라이싱 해줘야함
int visited[MAX_SIZE][MAX_SIZE] = { 0 }; // 방문 안했으면 0
int side[8] = { 1, 1, 0, -1, -1, -1, 0,1 }; // struct 로 하면 dir[8] 만들고 다시 초기화해줘야함
int up[8] = { 0, -1, -1, -1, 0, 1, 1,1 }; //  오른쪽부터 반시계방향
int w, h;
int landNum = 0;

void runTest();
void visit(int h, int w);
void reset();

int main() {

	while (1) {
		runTest();
		if (h == 0 && w == 0) {
			break;
		}
		printf("%d\n", landNum);
		reset();
	}

	return 0;
}
void runTest() {
	scanf("%d %d", &w, &h);
	for (int i = 0; i < h; i++) { // map 생성
		for (int j = 0; j < w; j++) {
			scanf("%d", &map[i][j]);
		}
	}

	for (int i = 0; i < h; i++) { // 섬찾으러가자~
		for (int j = 0; j < w; j++) {
			if (map[i][j] == 1 && visited[i][j] == 0) {
				landNum++;
				visit(i, j);
			}
		}
	}
}
void visit(int h,int w) { // 전달받은 섬과 연결된 놈들 다 방문
	visited[h][w] = 1;

	for (int i = 0; i < 8; i++) {
		if (map[h + up[i]][w + side[i]] == 1 && visited[h + up[i]][w + side[i]] == 0) { //  다음 노드도 섬이고 아직 visit 안했으면 stack 에 넣기
			visit(h+up[i], w+side[i]);
		}
	}

}

void reset() {
	for (int i = 0; i < h; i++) { 
		for (int j = 0; j < w; j++) {
			map[i][j] = 0;
			visited[i][j] = 0;
		}
	}
	landNum = 0;
}

MAX_SIZE 를 50으로 했다가 틀렸습니다 폭탄을 맞아 2시간 동안 뻘짓을 했다.

아직도 왜 오류가 난건지는 모르겠다.

이제 자료구조 수업때 배웠던 것들을 어떤식으로 사용하는지 이해가 간다.

나는 일단 하나의 케이스를 해결하는 코드를 만든 후 그 코드를 이용해 다른 테스트 케이스를 해결하는 방법으로 코드를 짰다. 또한 이후에 만든 코드들을 function 으로 묶어주어 보기 편하게 해주었다.

문제를 편하게 풀기 위해 선언을 다 Global 로 해주었는데 이 방법이 좋은 방법인지 확인해봐야겠다.

그리고 배열을 선언해줄때 arr[10][10] 형식으로 선언해주어 동적할당을 사용 안하려고 했는데 **arr 로 선언하여 동적할당을 할 수 있는 방법도 있다.