문제 : 안전영역
이 문제는 백조의 영역을 풀기 전에 선행되어야 할 문제라서 한번 풀어봤다.
문제는 어렵지 않으나, 왜 이렇게 생각하고 코드 작성을 했는지 한번 알아보자.
조건
첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다.
시간은 1초이나 최대 배열의 크기는 100 임으로 1초 즉 10^8 제곱을 넘어가지 않는 선에서 해결하면 된다. (사실상 자유롭게 풀어라라는 뜻,,) 그래프 탐색 방법 중 (BFS/DFS) 를 선택해서 해결하면 된다. (나는 둘다 선택해서 풀어봤다.)
만약 이러한 문제에서 시간 초과를 생각한다면 탐색을 효과적으로 할 수 있는 다른 알고리즘을 생각해야한다. -> 백조의 호수 문제를 꼭 풀어보자!(3197)
아래 코드를 보자.
for (int i = 0; i <= max_height; i++)
{
int temp[101][101] = { 0, };
memcpy(temp, board, sizeof(board));
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
if (temp[j][k] <= i)
{
temp[j][k] = 0;
}
}
}
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
{
if (temp[x][y] > 0 && visited[x][y] == 0) // 방문 배열이 존재해야하는가?
{
bfs(x, y, temp);
count += 1;
}
}
}
memset(visited, 0, sizeof(visited));
answer = std::max(answer, count);
count = 0;
}먼저 비가 왔을시에 어느 역영이 잠기게 될 것인가를 생각해야한다. 매커니즘은 이렇다.
===== 강수량 최대 지역 (max_height) + 잠김 지역 표시
for (int i = 0; i <= max_height; i++) { int temp[101][101] = { 0, }; memcpy(temp, board, sizeof(board)); for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if (temp[j][k] <= i) { temp[j][k] = 0; } } } for... continue..
===== 배열 복사 + DFS/BFS 과정
for (int x = 0; x < n; x++) { for (int y = 0; y < n; y++) { if (temp[x][y] > 0 && visited[x][y] == 0) // 방문 배열이 존재해야하는가? { bfs(x, y, temp); count += 1; } } } memset(visited, 0, sizeof(visited)); answer = std::max(answer, count); count = 0;
위의 두 과정이 하나의 for문으로 묶여서 작용하면 된다. 여기서 memset/memcpy(cstring) 가 필요하다 (alrogithm에 copy를 사용해도 무관 ) 이후 기초적인 BFS/DFS를 적용 시키면 된다. (BFS/DFS는 전체 코드에를 참고)
Q. 방문배열(visited)는 존재하는게 좋을까, 굳이 필요없을까?
-> 당연히 존재해야한다.
그 이유를 설명하자면,
5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7
위의 인풋에서 (0,0)이 BFS/DFS 과정의 첫번째 인풋 좌표로 들어갈 것이다. 이 후 자연스럽게 '다음 방문 좌표 (dx,dy[4]) 안에서 방문하면 되니까'라고 생각하면 굳이 필요없을 것 같지만 아래 같이 된다면
(0,0) -> (0,1) 순으로 방문했고, DFS/BFS 는 종료되고 Count를 +1 만큼 증가시킨다. 그리고 (0,1),(0,0) 은 방문 처리 된다. 그리고 다음 메인 함수에서 (0,1)를 방문하려고하면 이미 방문 됐기 때문에 넘어갈 수 있는 것이다. 그렇다면 방문 배열을 빼버린다면?
DFS/BFS 모두 메모리 초과 현상이 일어나게 된다. 하지만 간단한 입출력 예제를 통과하는데는 문제가 없었다. 이런 생각들은 카카오코딩테스트 처럼 모든 case 를 다 알려주고 체점을 하게 되면 문제 없지만, 보통 다른 회사들의 코딩테스트들은 Test case를 알려주지 않는다. 방문배열을 사용하지 않는다면, 눈에 보이는 TC만 통과하게 되어, 맞은것 처럼 보일 수 있다.
======= 전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
int n;
int board[101][101];
int visited[101][101];
int max_height;
int answer = 0u;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
std::vector<int> v;
void input()
{
std::cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
int temp = 0u;
std::cin >> temp;
max_height = std::max(temp, max_height);
board[i][j] = temp;
}
}
}
void bfs(int x, int y, int _board[][101])
{
std::queue<std::pair<int, int>> q;
q.push({ x,y });
while (!q.empty())
{
int _x, _y;
_x = q.front().first;
_y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++)
{
int nx, ny;
nx = _x + dx[i];
ny = _y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (_board[nx][ny] != 0 && visited[nx][ny] == 0)
{
visited[nx][ny] = 1;
q.push({ nx,ny });
}
}
}
}
void dfs(int x, int y, int _board[][101])
{
int nx, ny;
for (int i = 0; i < 4; i++)
{
nx = x + dx[i];
ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (_board[nx][ny] != 0 && visited[nx][ny] == 0)
{
visited[nx][ny] = 1;
dfs(nx, ny, _board);
}
}
}
int main()
{
input();
int count = 0;
for (int i = 0; i <= max_height; i++)
{
int temp[101][101] = { 0, };
memcpy(temp, board, sizeof(board));
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
if (temp[j][k] <= i)
{
temp[j][k] = 0;
}
}
}
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
{
if (temp[x][y] > 0 && visited[x][y] == 0) // 방문 배열이 존재해야하는가?
{
bfs(x, y, temp);
count += 1;
}
}
}
memset(visited, 0, sizeof(visited));
answer = std::max(answer, count);
count = 0;
}
std::cout << answer << std::endl;
return 0;
}```