[ 백준 2468번 ] 안전영역

백준 2468번 / 알고리즘 그래프 탐색 / 안전영역

 

백준 2468 - 안전영역

채점결과는 다음과 같다

	메모리	시간
1번째 방법	1228 KB	20 ms

 

문제 풀이

푸는 도중에는 몰랐는데 풀고 나니 DFS / BFS 문제였던 문제였다 그래프 탐색을 모르는 상태로 풀기 시작했는데
문제를 풀려고 여러 가지를 검색해 보니 그래프 탐색 방법이었다

1. 우선 먼저 땅이라고 지칭되는 맵(보드)의 행과 열을 타게팅 할 구조체를 하나 만들어준다
구조체를 사용해 주는 이유는 이 문제를 풀면서 이 행렬 타기팅을 계속하게 될 거 같아서 만들었다

typedef struct = 구조체
row = 행
col = 열
traget = 구조체 이름

2. 두 번째로 안전지역이 서로 연결되어 있는지 분리되어 있는지 확인하기 위한 상하좌우 체크를 할 행렬 체크 배열을 만들어준다

상 = check_row[1] check_col[1]
하 = check_row[0] check_col[0]
좌 = check_row[3] check_col[3]
우 = check_row[4] check_col[4]

3. 문제의 INPUT 값을 받아주면서 맵을 그리는 코드를 작성한다
맵을 그리면서 가장 큰 높이의 지점의 값을 복사해서 저장해둔다
그리고 방문 지점 체크를 하기 위한 배열도 모든 값을 false로 초기화 시켜줍니다

행 = i
열 = j
맵의 최대 높이 지점 = h_max
방문 체크 배열 = visit[][]

4. 2중 for 문을 사용해서 맵을 처음부터 순회를 해줍니다
순회를 하면서 상하좌우를 탐색할 때 방해하는 중복 방문을 없애기 위해 한번 방문한 곳은 체크해 줍니다

첫 번째 조건문을 달아줍니다
물이 잠기는 높이보다 높은 값이면서 방문하지 않았던 인덱스라면 queue에 인덱스 정보를 넣어줍니다
if ( data[i][j] > height && !visit[i][j] ) q.push( {i, j} )
이렇게 queue에 푸시를 하고 나면 방문 처리를 해줍니다
visit[i][j] = true

5. queue 데이터가 빌 때까지 무한 반복을 해주는 반복문을 하나 생성해 줍니다
queue 데이터가 비지 않았다면 아직 상하좌우로 연결된 지점이 있다는 의미입니다
연결된 지점은 곧 같은 공간으로 인식돼서 안전 구역 + 1로 카운팅 되므로 중요한 개념입니다
while( !q.empty() )

생성된 반복 문안에 코드를 작성해 줍니다
미리 만들어두었던 구조체에 queue의 들어가 있던 맵 좌표를 대입해 줍니다
target t = q.front()
t row = i
t col = j
대입을 하고 나면 queue에서 대입한 데이터는 방문과 계산 처리를 다 완료했고
다음 queue 데이터를 위해 빼줍니다
q.pop()

6. 이제 꺼내온 인덱스 좌표의 상하좌우를 체크할 for 문 하나를 더 만들어줍니다
for ( k = 0; k < 4; k++ )
int row = t.row + check_row[k]
int col = t.col + check_col[k]

상하좌우를 체크하는 도중에 인덱스가 맵 크기를 벗어났는지 체크를 해주고 맵을 벗어났다면 continue 를 해줘서
다음 코드를 스킵 해줍니다 벗어나지 않았다면 다음 코드를 실행시켜줍니다
좌표 인덱스 상하좌우 중에 방문을 하지 않았던 곳이며 지정된 높이보다 높은 곳은 queue에 넣어줍니다
그리고 푸시를 하는 동시에 방문 처리도 해줍니다

if ( row < 0 || col < 0 || row >= n || col >= n) continue
if ( !visit[row][col] && data[row][col] > height)
q.push({row, col});
visit[row][col] = true;

이렇게 반복문을 계속 돌리면서
반복문이 끝나기 전 queue에 새로운 데이터가 들어오지 않는다면 연결된 안전지역은 끝이므로
안전지역 카운팅을 하나 플러스해 줍니다
하나의 안전지역이 완성되었습니다
safe++

이렇게 방문지역을 건너뛰면서 방문되지 않은 곳만 탐색을 하고 그 주위를 탐색해서 연결된 지역을 확인해
다시 안전지역을 만들어주고 반복하면서 맵 모든 인덱스를 탐색이 완료되면 모든 반복문을 종료합니다

7. 이렇게 카운팅 된 안전지역을 문제 조건에 맞게 다시 찾아줍니다
높이의 제한은 제공된 맵 인덱스 높이 중에 이 가장 높은 h_max 값까지 찾아줍니다
문제조건: 지역의 모든 높이 경우의 수 중에 안전지대 최대 개수를 찾기 위해
go back 함수와 max 함수를 사용해 줍니다

if ( height != h_max)
height++
result = max(result, safe)
goto back

goto 문을 사용하면 back: <- 이 지점부터 다시 시작합니다
이렇게 모든 경우의 수를 탐색해서 안전지역 최대 개수를 구하고 출력해 주면 됩니다

 

코드

#include <stdio.h>
#include <algorithm>
#include <queue>

using namespace std;

typedef struct {
	int row;
	int col;
} target;

int check_row[] = {-1, 1, 0, 0};
int check_col[] = {0, 0, -1, 1};

int main() {
	int n;
	int i, j, k;
	int height = 0;
	int safe = 0;
	int h_max = 0;
	int result = 0;
	int data[100][100];
	bool visit[100][100];
	queue<target> q;

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &data[i][j]);
			h_max = max(h_max, data[i][j]);
		}
	}

	back:
	safe = 0;
	for ( i = 0; i < n; i++ ) {
		for ( j = 0; j < n; j++ ) {
			visit[i][j] = false;
		}
	}
	for ( i = 0; i < n; i++ ) {
		for ( j = 0; j < n; j++ ) {
			if( data[i][j] > height && !visit[i][j]) {
				q.push({i, j});
				visit[i][j] = true;

				while(!q.empty()) {
					target t = q.front();
					q.pop();

					for ( k = 0; k < 4; k++ ) {
						int row = t.row + check_row[k];
						int col = t.col + check_col[k];

						if ( row < 0 || col < 0 || row >= n || col >= n ) continue;
						if ( !visit[row][col] && data[row][col] > height ) {
							q.push({row, col});
							visit[row][col] = true;
						}
					}
				}
				safe++;
			}
		}
	}
	//printf("%d\n", safe);
	if ( height != h_max ) {
		height++;
		result = max(result, safe);
		goto back;
	}
	printf("%d", result);
}