깊이 우선 탐색(Depth-First Search)

11724 연결 요소의 개수(3/31)

dfs bfs로 그래프를 순회하고 나서 방문되지 않은 vertex가 있으면 끊어진 그래프다 그래서 이 새로운 dfs(bfs)가 몇 번 다시 시작됐는지 구한다
1) 정점의 개수, 간선의 개수를 입력받는다
2) 간선이 연결하는 두 정점의 번호를 입력받아 연결한다
3) dfs로 완전탐색을 진행하고 각각의 정점탐색 시작마다 방문 여부를 책크해 조건 해당시 count를 올려준다
4) 올린 count 연결 요소의 개수를 출력한다

@ https://rolypolytoy.tistory.com/35
@ https://aeunhi99.tistory.com/59

 

1260 DFS와 BFS(4/1)

 

1012 유기농 배추(4/1)

@ https://4z7l.github.io/2020/09/10/algorithms-boj-1012.html

4963 섬의 개수(4/1)

@memset -> 테스트 케이스가 여러개일 때초기화 해주는 함수

#include <cstring>

//void* memset(void* ptr, int value, size_t num);
memset(초기화할 배열 시작점, 초기화 값, 메모리의 길이);

@ https://jdselectron.tistory.com/53

 

1743 음식물 피하기(4/1)
좌표를 dfs로 순회하고 가장 넓은 부분의 크기를 출력한다

@ https://scarlettb.tistory.com/96

2667 단지 번호 붙이기(4/1)
지도를 dfs로 4방향을 순회하고 vetor와 sort를 이용해 넓이가 작은 그래프부터 출력한다

@ https://guiyum.tistory.com/37

 

2583 영역 구하기(4/3)
모눈종이를 0으로 초기화 시키고 x,y좌표 값을 이용해 직사각형 영역을 1으로 만들어준다. 0 부분을 dfs로 4방향으로 탐색하고 1로 막혀 더 이상 탐색할 수 없을 때까지 0을 1로 만들어주면서 탐색한다. vector와 sort를 이용해 넓이가 작은 그래프부터 넓이를 출력한다.

@ https://rile1036.tistory.com/48

2468 안전영역(4/3)
비가 내리는 높이가 0부터 100까지인 경우를 모두 구해본다. 0으로 초기화 시킨 후 비가 내리는 높이 이하인 수는 1으로 만들어 주고 나머지는 dfs로 그래프가 몇 개 있는 지 구한다. 그 중 최대 값을 출력한다.

@ https://rile1036.tistory.com/47

10026 적록색약(4/3)
R, G, B 영역을 dfs로 그래프 개수를 한 번 세어주고 G영역을 R로 만들어 주고 dfs로 그래프 개수를 세어준다.
@ R, G, B 문자이므로 char로 선언

char photo[100][100];

@ G를 R로 바꿀 때

if (photo[i][j] == 'G') photo[i][j] = 'R';

@ https://4z7l.github.io/2021/02/02/algorithms-boj-10026.html

 

9466 텀 프로젝트
11403 경로 찾기
10265 MT

 

*bfs로 4방향 탐색할 경우

int map[100][100];
bool visited[100][100] = { false };
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

void dfs(int x, int y) {
	visited[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
		if (!visited[nx][ny] && map[x][y] == map([nx][ny]) {
			dfs(nx, ny);
		}
	}
}