(cpp) Baekjoon 14502번 문제 ‘연구소’ - 구현, 그래프이론, 브루트포스, 그래프탐색, 너비우선탐색

on Programming Languages

Baekjoon 14502번 문제 ‘연구소’ - 구현, 그래프이론, 브루트포스, 그래프탐색, 너비우선탐색

문제

예제입력2에 대한 문제풀이

image 1. 벽 3개를 세우는 경우는 브루트포스로 경우의 수를 모두 고려해야 한다.

2. 벽을 세울 때마다 감염 시뮬레이션 실행한다.

3. 감염된 상태에서 안전영역 구한다. 이 때 map의 0갯수 구하면 됨.

4. 매 case별로 안전영역 크기 구하고 최대값으로 계속해서 갱신한다.

image
image

(cpp) Baekjoon 7569번 문제 ‘토마토’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색 (토마토7576과 다른 ver)

on Programming Languages

Baekjoon 7569번 문제 ‘토마토’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제

예제입력2에 대한 문제풀이

image

1. 익은 토마토가 있는 칸부터 시작한다. 7576번 토마토 문제는 2차원 배열이였으나 이번엔 상자를 위로 쌓아올리는 3차원 배열이다. 따라서, 토마토의 위치는 [i,j.k]로 표현한다. 순서대로, 높이,행,열 이다. 즉 예제2번의 시작큐는 = [2,2,3]이다. ‘2층의 2행 3열’이라는 의미.

2. [2,2,3]에서 시작했을 때 갈 수 있는 곳은 왼[2,2,2],오[2,2,4],위[2,1,3],아[2.3,3],아래층[1,2,3]이다. 칸의 위치가 3차원 배열인 것과 방문 후보가 4개에서 6개로 늘었다는 것 외에는 7576번과 같은 방식으로 해결할 수 있다.

코드

```cpp #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std;

(cpp) Baekjoon 10026번 문제 ‘적록색약’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

on Programming Languages

Baekjoon 10026번 문제 ‘적록색약’ - 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제

예제입력1에 대한 문제풀이

image 1. 시작점과 상하좌우로 인접한 지점들을 탐색하여 해당 지점과 같은 색깔이면 같은 그룹으로 분류되고, 그렇지 않으면 다른 그룹이 된다. 이떄, 색약이 있는 사람은 R과 G를 같은 그룹으로 본다.

2. 색약 없는 사람의 check박스와 색약 있는 사람의 check박스를 각각 만든다.

3. [1,1]을 시작큐에 넣었을 떄 탐색 후보군은 [1,2],[2,1]이 된다. check1[1][1]=1로 체크했을 때, [1,2]는 [1,1]과 같으므로 ‘check1[1][2]=check1[1][1]’이 되고, [2,1]은 [1,1]과 다르므로 ‘check1[2][1] = check1[1][1] + 1’ 이 된다. 반면, 색약이 있는 사람의 check2의 경우 ‘check2[1][2] = check2[2][1] = check[1][1]’ 이다.

Pagination