백준 2573번 빙산

문제 링크입니다: https://www.acmicpc.net/problem/2573

쉬운 난이도의 BFS(Breadth First Search) 혹은 DFS(Depth First Search) 알고리즘 문제였습니다.

하지만, 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 조건을 확인하지 못한 저는 답이 0인 경우에 대해 처리하지 않아 왜맞틀을 반복하면서 8번 시간초과가 발생했습니다...

소스코드에는 BFS, DFS 전부 선언이 되어있는데 저는 처음에 BFS 기법을 통해 풀었기 때문에 melt 함수도 BFS 기법과 유사하게 동서남북에 0이 몇개인지 탐색합니다.

시간초과가 계속 발생해서 저는 실행시간을 줄이기 위해 stdio와 sync를 끊었고 첫 번째와 마지막의 열과 행은 무조건 바다이기 때문에 첫 번째와 마지막의 열과 행에 대해서는 탐색을 하지 않았습니다.

#include <iostream>

#include <queue>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 300;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int N, M;

int graph[MAX][MAX];

bool visited[MAX][MAX];

 

void melt(void)

{

        int copy[MAX][MAX]; //기존의 빙산 복사

        for (int y = 0; y < N; y++)

                 for (int x = 0; x < M; x++)

                         copy[y][x] = graph[y][x];

 

        for(int y = 1; y < N - 1; y++)

                 for(int x = 1; x < M - 1; x++)

                         if (copy[y][x])

                         {

                                 int cnt = 0;

                                 for (int i = 0; i < 4; i++)

                                 {

                                          int nextY = y + moveDir[i].y;

                                          int nextX = x + moveDir[i].x;

 

                                          if (copy[nextY][nextX] == 0)

                                                  cnt++; //동서남북 0인만큼 감소

                                 }

                                 //높이는 0 이상

                                 graph[y][x] = max(copy[y][x] - cnt, 0);

                         }

}

 

/*

//전형적인 BFS

void BFS(int y, int x)

{

        queue<pair<int, int>> q;

        q.push(make_pair(y, x));

        visited[y][x] = true;

 

        while (!q.empty())

        {

                 int curY = q.front().first;

                 int curX = q.front().second;

                 q.pop();

                

                 for (int i = 0; i < 4; i++)

                 {

                         int nextY = curY + moveDir[i].y;

                         int nextX = curX + moveDir[i].x;

 

                         if (1 <= nextY && nextY < N - 1 && 1 <= nextX && nextX < M - 1)

                                 if (graph[nextY][nextX] && !visited[nextY][nextX])

                                 {

                                          visited[nextY][nextX] = true;

                                          q.push(make_pair(nextY, nextX));

                                 }

                 }

        }

}

*/

 

void DFS(int y, int x)

{

        visited[y][x] = true;

 

        for (int i = 0; i < 4; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if (1 <= nextY && nextY < N - 1 && 1 <= nextX && nextX < M - 1)

                         if (graph[nextY][nextX] && !visited[nextY][nextX])

                                 DFS(nextY, nextX);

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

        cin >> N >> M;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < M; j++)

                         cin >> graph[i][j];

 

        int year = 0;

        while (1)

        {

                 memset(visited, false, sizeof(visited));

 

                 bool result = false;

 

                 int cnt = 0;

                 //마지막 열과 행은 전부 바다

                 for (int y = 1; y < N - 1; y++)

                         for (int x = 1; x < M - 1; x++)

                                 if (graph[y][x] && visited[y][x] == false)

                                 {

                                          cnt++;

                                          if (cnt == 2)

                                          {

                                                  result = true;

                                                  break;

                                          }

                                          DFS(y, x);

                                 }

 

                 if (result)

                         break;

                 //기저 사례

                 if (cnt == 0)

                 {

                         year = 0;

                         break;

                 }

 

                 melt(); //빙산이 동서남북에 바다가 있는 만큼 녹는다

                 year++; //일년이 지나면

        }

       

        cout << year << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~