(코딩테스트) 백준-3197번 백조의 호수(bfs)

1) 문제 

 

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

 

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

 

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

 

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

 

예제 입력 1

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

예제 출력 1 

3

 

2) 풀이

2.1)  입력조건

- dfs/bfs로 문제 풀이 

2.2)  풀이과정 

- 백조가 만날 수 있는지를 true || false 로 반환

- 백조가 못 만나면 while문을 진행

- 다음 좌표값이 '.'이 아니면 temp q에 추가하여 진행 

- 다음 좌표값이 '.'이면 생략 

- 모든 !'.'를 만나서 temp에는 다음날 진행 될 녹은공간('X' - > '.'로 바뀐 공간) 담긴

- q = temp로 담아서 다음날 진행 

- 메모리 초과 ㅠㅠ 

2.3)  코드

#include <bits/stdc++.h>
using namespace std;

int r, c, visited[1504][1504], cnt;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
vector<pair<int, int>> v;
char a[1504][1504];
queue<pair<int, int>> q;

bool bfs(pair<int, int> start, pair<int, int> end)
{
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int>> q;
    q.push(start);
    while (q.size())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        if (y == end.first && x == end.second)
        {
            return true;
        }
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= r || nx >= c || visited[ny][nx])
                continue;
            if (a[ny][nx] == '.')
            {
                visited[y][x] = 1;
                q.push({ny, nx});
            }
        }
    }
    return false;
}

int main()
{
    cin >> r >> c;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == '.')
            {
                q.push({i, j});
            }
            else if (a[i][j] == 'L')
            {
                v.push_back({i, j});
            }
        }
    }
    while (!bfs(v[0], v[1]))
    {
        cnt++;
        queue<pair<int, int>> temp;
        while (q.size())
        {
            int y, x;
            tie(y, x) = q.front();
            q.pop();
            for (int i = 0; i < 4; i++)
            {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny < 0 || nx < 0 || ny >= r || nx >= c)
                    continue;
                if (a[ny][nx] != '.')
                {
                    a[ny][nx] = '.';
                    temp.push({ny, nx});
                }
            }
        }
        q = temp;
    }
    cout << cnt;
}

3) 해설

3.1)  메모리 초과 

- 백조의 탐색 범위를 처음부터 계속 탐색 -> 기존의 탐색 범위는 무시, tempQ를 통해서 새로운 탐색 범위 지정

- visited_water부재 : visited를 처리 하지 않아서 계속 탐색 -> visited추가

- while(bfs) : 조건문에 bfs로 시간 복잡도 증가 -> 탈출 조건 변경

3.2)  사용된 알고리즘

    while (true)
    {
        if (move_swan())
            break;
        meltig_water();
        waterQ = water_tempQ;
        swanQ = swan_tempQ;
        Qclear(water_tempQ);
        Qclear(swan_tempQ);
        cnt++;
    }

 

3.3)  완성된 코드

#include <bits/stdc++.h>
using namespace std;

int r, c, visited_swan[1504][1504], visited[1504][1504], cnt, swanY, swanX, y, x;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
char a[1504][1504];
queue<pair<int, int>> swanQ, swan_tempQ, waterQ, water_tempQ;
void Qclear(queue<pair<int, int>> &q)
{
    queue<pair<int, int>> empty;
    swap(q, empty);
}
void meltig_water()
{
    while (waterQ.size())
    {
        tie(y, x) = waterQ.front();
        waterQ.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= r || nx >= c || visited[ny][nx])
                continue;
            if (a[ny][nx] == 'X')
            {
                visited[ny][nx] = 1;
                a[ny][nx] = '.';
                water_tempQ.push({ny, nx});
            }
        }
    }
}

bool move_swan()
{
    while (swanQ.size())
    {
        tie(y, x) = swanQ.front();
        swanQ.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || nx < 0 || ny >= r || nx >= c || visited_swan[ny][nx])
                continue;
            visited_swan[ny][nx] = 1;
            if (a[ny][nx] == '.')
                swanQ.push({ny, nx});
            else if (a[ny][nx] == 'X')
                swan_tempQ.push({ny, nx});
            else if (a[ny][nx] == 'L')
                return true;
        }
    }
    return false;
}

int main()
{
    cin >> r >> c;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == '.' || a[i][j] == 'L')
            {
                visited[i][j] = 1;
                waterQ.push({i, j});
            }
            if (a[i][j] == 'L')
            {
                {
                    swanY = i;
                    swanX = j;
                }
            }
        }
    }
    swanQ.push({swanY, swanX});
    visited_swan[swanY][swanX] = 1;
    while (true)
    {
        if (move_swan())
            break;
        meltig_water();
        waterQ = water_tempQ;
        swanQ = swan_tempQ;
        Qclear(water_tempQ);
        Qclear(swan_tempQ);
        cnt++;
    }
    cout << cnt;
}