4991번 로봇 청소기

https://www.acmicpc.net/problem/4991

단순 여러 번 BFS를 돌리는 문제인줄 알았는데, 그게 아니었다..

그래서, 더러운 곳들과 로봇 사이의 모든 거리를 구하는 것까지는 생각하였지만, 구현을 잘 못 했다.

다른 분의 코드를 참고하면서 구현했다.

아마 이 분 코드가 없었더라면, 구현을 못 했을 것이다.

다시 한 번, 구현의 중요성과 (나한테는) 난이도 매우 높은 문제여서 좋기도 하다.

다시 한 번 꼭 풀어볼 문제이다!!

참고로, next_permutation을 이용한 풀이 방법도 있다.

http://sejinik.tistory.com/69

코드는 총 3개 올린다.

1. 다른 분 코드 참고하여, 구현한 코드

2. 혼자서 다시 구현해보았다.

3. 시간 초과 코드.(backtracking 할 때, 방문 처리 배열이 이중 배열)

<정답 코드, 다른 분 코드 참고>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
#define INF 21*21*21*21
 
int w = 0, h = 0;
 
char Map[21][21];
 
vector<pair<pair<int, int>, int> > v;
 
int ry = 0, rx = 0;
 
int result = 0;
 
int dist[21][21][21][21] = { 0, };
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
// 백트래킹. 순열. 최고 경우의 수 = 10!
void BackTracking(int pos, pair<int, int> now, int sum)
{
    if (pos == v.size())
    {
        if (sum < result) result = sum;
        
        return;
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        pair<int, int> next = v.at(i).first;
 
        if (v.at(i).second == 1) // 이미 처음에 {ry, rx}를 했으므로, 이후에 로봇은 적용할 필요가 없다.
        {
            v.at(i).second = 0; // 바꿔주고
 
            BackTracking(pos + 1, next, sum + dist[now.first][now.second][next.first][next.second]);
 
            v.at(i).second = 1; // 다시 원상태
        }
    }
}
 
int main(void)
{
    while (1)
    {
        scanf("%d %d", &w, &h);
 
        if (w == 0 && h == 0) break;
 
        result = INF;
 
        if (!v.empty()) v.clear();
 
        for (int i = 0; i < 21; i++)
            for (int j = 0; j < 21; j++)
                for (int k = 0; k < 21; k++)
                    for (int z = 0; z < 21; z++)
                        dist[i][j][k][z] = INF;
        /*
        INF로 초기화 해줘야 한다.
        왜냐하면, 백트래킹으로 계산할 때에, 
        sum이 INF를 초과하는지 안 하는지 여부에 따라 정답이 달라진다.
        */
 
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                cin >> Map[i][j];
                
                if (Map[i][j] == 'o') // 로봇
                {
                    v.push_back({ {i, j}, 0 });
 
                    ry = i;
                    rx = j;
                }
                else if (Map[i][j] == '*') // 더러운 칸
                {
                    v.push_back({ {i, j}, 1 });
                }
            }
        }
 
        for (int i = 0; i < v.size(); i++)
        {
            int cury = v.at(i).first.first;
            int curx = v.at(i).first.second;
 
            int ret = 0;
 
            queue<pair<int, int> > q;
 
            bool visit[21][21] = { false, };
 
            q.push({ cury, curx });
 
            visit[cury][curx] = true;
 
            while (!q.empty())
            {
                int qSize = q.size();
 
                while (qSize--)
                {
                    int y = q.front().first;
                    int x = q.front().second;
 
                    q.pop();
 
                    /*
                    처음에 (cury != y || curx != x) 라는 조건도 추가했었는데,
                    생각해보니 이렇게하면 안 되었다. 모든 쓰레기들과 로봇
                    이 모든 것들 사이의 거리를 dist 배열에 저장했어야 했다.
                    또한, 하나만 갱신하고 stop = true로 바꿔, break를(BFS의 return이라고 생각)
                    했었는데, 이것도 틀리다.
                    */
 
                    if (Map[y][x] == '*' || Map[y][x] == 'o') dist[cury][curx][y][x] = ret;
                    
                    for (int i = 0; i < 4; i++)
                    {
                        int ny = y + dy[i];
                        int nx = x + dx[i];
 
                        if (ny < 0 || ny >= h || nx < 0 || nx >= w || Map[ny][nx] == 'x' || visit[ny][nx]) continue;
 
                        q.push({ ny, nx });
                        visit[ny][nx] = true;
                    }
                }
 
                ++ret;
            }
        }
 
        BackTracking(1, { ry, rx }, 0);
        // pos는 1부터 시작. 왜냐하면, 이미, {ry, rx}를 주고 시작하기 때문이다.
 
        if (result >= INF) printf("-1\n");    
        else printf("%d\n", result);
    }
 
    return 0;
}

<다시 구현해보았다. 정답 코드>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int w = 0, h = 0;
 
char room[22][22];
 
vector<pair<int, int> > dirty;
 
int dist[11][11] = { 0, }; // [행][열] = [행]에서 [열]로 가는 최단 거리
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
bool visit_bt[11] = { false, }; // backtracking() 함수 전용 visit 방문 처리 배열
 
int result = 0;
 
void backtracking(int now, int total, int pos)
{
    if (pos == dirty.size())
    {
        result = min(result, total);
 
        return;
    }
 
    for (int next = 1; next < dirty.size(); next++) // 0은 무조건 포함시켜야함.
    {
        if (now == next) continue;
 
        if (!visit_bt[next])
        {
            visit_bt[next] = true;
 
            total += dist[now][next];
 
            backtracking(next, total, pos + 1);
 
            total -= dist[now][next];
 
            visit_bt[next] = false;
        }
    }
}
 
int BFS(pair<int, int> s, pair<int, int> e)
{
    queue<pair<int, int> > q;
 
    bool visit[22][22] = { false, };
 
    q.push(s);
 
    visit[s.first][s.second] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            if (r == e.first && c == e.second) return ret;
            
            for (int i = 0; i < 4; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= h || x < 0 || x >= w || visit[y][x] || room[y][x] == 'x') continue;
 
                q.push({ y, x });
                visit[y][x] = true;
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
void init()
{
    memset(visit_bt, false, sizeof(visit_bt));
 
    for (int i = 0; i < 11; i++) for (int j = 0; j < 11; j++) dist[i][j] = -1;
 
    result = 22 * 22;
 
    dirty.clear();
}
 
int main(void)
{
    while (1)
    {
        scanf("%d %d", &w, &h);
 
        if (w == 0 && h == 0) break;
 
        init();
    
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                scanf(" %1c", &room[i][j]);
 
                if (room[i][j] == 'o') dirty.insert(dirty.begin(), { i, j });
                else if (room[i][j] == '*') dirty.push_back({ i, j });
            }
        }
 
        bool stop = false;
 
        for (int i = 0; i < dirty.size(); i++)
        {
            for (int j = 0; j < dirty.size(); j++)
            {
                if (i >= j) continue; // 시간 단축
 
                dist[i][j] = dist[j][i] = BFS(dirty.at(i), dirty.at(j));
 
                if (dist[i][j] == -1)
                {
                    stop = true;
                    break;
                }
            }
 
            if (stop) break;
        }
 
        if (stop)
        {
            printf("-1\n");
            continue;
        }
 
        backtracking(0, 0, 1);
 
        printf("%d\n", result);
    }
 
    return 0;
}

<시간 초과, 왜 시간 초과인지 잘 모르겠다.>

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int w = 0, h = 0;
 
char room[22][22];
 
vector<pair<int, int> > dirty;
 
int dist[11][11] = { 0, }; // [행][열] = [행]에서 [열]로 가는 최단 거리
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
bool visit_bt[11][11] = { false, }; // backtracking() 함수 전용 visit 방문 처리 배열
 
int result = 0;
 
void backtracking(int now, int total, int pos)
{
    if (pos == dirty.size())
    {
        result = min(result, total);
 
        return;
    }
 
    for (int next = 1; next < dirty.size(); next++) // 0은 무조건 포함시켜야함.
    {
        if (now == next) continue;
 
        if (!visit_bt[now][next])
        {
            visit_bt[now][next] = true;
 
            total += dist[now][next];
 
            backtracking(next, total, pos + 1);
 
            total -= dist[now][next];
 
            visit_bt[now][next] = false;
        }
    }
}
 
int BFS(pair<int, int> s, pair<int, int> e)
{
    queue<pair<int, int> > q;
 
    bool visit[22][22] = { false, };
 
    q.push(s);
 
    visit[s.first][s.second] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            if (r == e.first && c == e.second) return ret;
            
            for (int i = 0; i < 4; i++)
            {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= h || x < 0 || x >= w || visit[y][x] || room[y][x] == 'x') continue;
 
                q.push({ y, x });
                visit[y][x] = true;
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
void init()
{
    memset(visit_bt, false, sizeof(visit_bt));
 
    for (int i = 0; i < 11; i++) for (int j = 0; j < 11; j++) dist[i][j] = -1;
 
    result = 22 * 22;
 
    dirty.clear();
}
 
int main(void)
{
    while (1)
    {
        scanf("%d %d", &w, &h);
 
        if (w == 0 && h == 0) break;
 
        init();
    
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                scanf(" %1c", &room[i][j]);
 
                if (room[i][j] == 'o') dirty.insert(dirty.begin(), { i, j });
                else if (room[i][j] == '*') dirty.push_back({ i, j });
            }
        }
 
        bool stop = false;
 
        for (int i = 0; i < dirty.size(); i++)
        {
            for (int j = 0; j < dirty.size(); j++)
            {
                if (i >= j) continue;
 
                dist[i][j] = dist[j][i] = BFS(dirty.at(i), dirty.at(j));
 
                if (dist[i][j] == -1)
                {
                    stop = true;
                    break;
                }
            }
 
            if (stop) break;
        }
 
        if (stop)
        {
            printf("-1\n");
            continue;
        }
 
        backtracking(0, 0, 1);
 
        printf("%d\n", result);
    }
 
    return 0;
}