개요
비트필드를 이용한 DP를 최근 재밌게 풀고 있어서 잡았던 문제입니다.
BFS와 TSP를 잘 조합하면 풀립니다.
먼지의 개수가 최대 10개기 때문에 순열 탐색에 시간 복잡도가 \(O(n!)\)인 브루트포스로도 가능합니다.
10!은 300만 언저리로 버티기 쉽기 때문이죠. 근데 전 마침 외판원 순회 문제를 풀어본 김에 다르게 풀었습니다.
문제
오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.
방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
.: 깨끗한 칸
*: 더러운 칸
x: 가구
o: 로봇 청소기의 시작 위치
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.
테스트 케이스 (요약)
| 입력 | 출력 |
| 7 5 ....... .o...*. ....... .*...*. ....... 0 0 |
8 |
풀이
아이디어 정리
문제를 딱 보면 풀이 방법이 여러가지가 생각납니다.
알고리즘 분류도 뭔가 짬뽕이 많이 돼있죠.
모든 순열을 탐색 하라는듯한 브루트포스, TSP에서 흔히 쓰이는 비트필드를 이용한 DP를 암시하는 듯한 비트마스킹 태그도 보이죠.
뭐 이것들은 다 뒤로 미루고 일단 문제를 어떻게 풀어야할지부터 생각해봅시다.
일단 입력에서 방은 W*H의 2차원 타일들로 주어집니다.
일단 행렬은 모든 먼지를 순회하는 최단 경로를 계산하기 그리 좋진 않습니다. 단순히 로봇 청소기를 기준으로 BFS를 돌려서 가장 먼저 닿는 먼지부터 청소하는 그리디 같은 접근을 생각 해봤지만 그리디는 '그 당시의 최선'을 고르는거지 언제나 최적을 골라주는게 아니기 때문에 그리디가 골라주는 경로가 언제나 최적이라고 할 수 없습니다.
물론 예시로 그린 저 그림에선 그리디로 해결할 수 있지만 과연 모든 TC에서 그게 성립할지를 생각해봐야 합니다.
이거까지 설명하면 너무 길어지니 스킵하겠습니다.
아무튼 여기서 로봇 청소기와 먼지를 하나의 '노드'로 처리하고 노드 사이를 간선으로 이은 뒤 그 간선의 가중치를 노드와 노드의 최단 거리로 둘 경우 매우 쉬워집니다.
물론 이 노드들 사이의 최단거리는 모든 노드에서 다 구해줘야 합니다. 간선을 통해 다른 노드로 이동했다면 그 노드에서 또 다른 노드로 이동해야 하니까요.
이렇게 모두 최단 거리를 구했다면 이제 TSP를 사용할 수 있습니다. 외판원 순회랑 똑같아요. 단지 차이점은 도시가 먼지인거고 이동 비용이 거리인거죠.
그래서 최단거리는 어떻게 구하냐구요? 당연하게도 BFS를 사용합니다. 모든 노드를 돌아보면서 BFS를 한번씩 돌려줄거에요.
그 뒤에 그 노드들을 TSP를 통해 순회하면서 최단 거리를 구할겁니다.
코드로 풀기
아이디어가 나왔다면 코드로 푸는건 간단하죠.
일단 입력으로 들어오는 테스트 케이스의 갯수는 정해져있지 않습니다. 그러니 while(true)를 돌다가 break를 알잘딱하면 됩니다.
이런류의 문제들은 main함수가 진짜 간결해질 수 있어서 기분이 좋습니다.
일단 대강 풀이에 쓰이는 메인 함수에서 bool값을 반환하도록 한 다음에, 방의 가로, 세로 입력을 받아 둘 중 하나라도 0이라면 return false를 해주면 됩니다. (문제에선 입력이 둘 다 0일때긴 하지만 방의 가로나 세로가 0인 경우 방이 존재할 수 없기 때문에 들어올 수 없는 입력)
bool solve()
{
int w,h;
cin >> w >> h;
if(w == 0 || h == 0)
return false;
return true;
}
이렇게 되면 main함수는 한 줄로 끝납니다.
int main()
{
while(solve());
}
// return 0; 는 스킵할게요.뭔가 간지가 나죠.
문제 제출 당시엔 습관처럼 붙이는 입출력 딜레이를 줄이는 매크로를 붙여서 2줄이긴 합니다.
이제 딴소리는 집어치우고 마저 풀어봅시다.
일단 입력을 받을 때 한가지 고려 해야하는게 있습니다.
로봇 청소기와 먼지를 노드로 만들고 그 노드 사이를 잇는 간선을 만든다고 했었죠? 근데 이 때 필수요소가 바로 노드의 번호입니다.
흔히 사용하는 인접 행렬을 봅시다. adj[i][j] = w. i번 노드에서 j번 노드로 가는 간선의 가중치가 w라는거죠. 저는 이 i와 j가 필요해요.
하지만 제가 받는 입력은 그냥 무수한 점과 동그라미와 별 뿐입니다.
그러니, 살짝의 보정을 거쳐야겠죠.
로봇 청소기는 탐색의 시작점이 될테니 무조건 0을 할당해줍니다. 딴 수여도 상관은 없어요. 그 뒤에 입력을 받으며 *이 나오면 그 *이 나온 위치에 dustCount++을 대신 집어넣습니다.
그리고 최단 거리를 구하기 위해 노드 전체를 순환해야하기 때문에 nodes배열을 만들어 미리 좌표를 저장합니다. 방에 존재하는 먼지의 개수도 같이 세어줍니다.
vector<vector<char>> map(h + 1, vector<char>(w + 1));
dustCount = 1;
pair<int, int> nodes[11];
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
cin >> map[i][j];
if (map[i][j] == '*')
{
map[i][j] = dustCount + '0';
nodes[dustCount++] = { j,i };
}
else if (map[i][j] == 'o')
{
map[i][j] = '0';
nodes[0] = { j,i };
}
}
}이렇게 되면 모든 노드마다 넘버링이 되었기 때문에 인접 행렬을 사용할 수 있습니다.
그 뒤에 이렇게 인접 행렬을 만들고 nodes를 순환하면서 bfs함수를 호출하면 됩니다.
vector<vector<int>> adj(dustCount + 1, vector<int>(dustCount + 1, VERY_BIG_NUMBER));
for (int i = 0; i <= dustCount; i++)
{
bfs(map, adj, nodes[i].first, nodes[i].second, i);
}
참고로 bfs 함수는 요로코롬 생겼습니다. 굳이 map과 adj를 매개변수로 넘겨주는 이유는 전역 변수로 두기엔 애매해서 그렇습니다. 걍 배열이면 테스트 케이스마다 memset 하면서 초기화를 하면 되는데 처음 적을 때 vector로 적어서 이케 됐어요
void bfs(vector<vector<char>>& map, vector<vector<int>>& adj, int x, int y, int node)
그리고 저는 BFS를 돌릴 때 queue에 pair 대신 struct를 넣는걸 좋아합니다. 그냥 더 이쁘고 더 짜기 편합니다. 대충 이렇게 생겼는데...
struct distInfo
{
int count;
pair<int, int> curPos;
bool moveTo(vector<vector<char>>& map, pair<int, int> dir)
{
curPos.first += dir.first;
curPos.second += dir.second;
if (isOutOfRange())
return false;
if (visited[COORD(curPos)])
return false;
if (map[COORD(curPos)] == 'x')
return false;
count++;
return true;
}
bool isOutOfRange()
{
return curPos.first < 0 || curPos.second < 0 || curPos.first >= w || curPos.second >= h;
}
};별건 없고 그냥 이동하는 함수 하나 만들어주고 이동하는 위치가 올바른지 검사해줍니다. 이러면 BFS 로직이 간결해져서 좋죠.
간단하게 중복 탐색 방지를 위한 visited배열 하나 만들어주고 BFS를 시작 할때마다 false로 초기화해주고 쭉 순회하면서 인접 행렬을 채웁니다.
void bfs(vector<vector<char>>& map, vector<vector<int>>& adj, int x, int y, int node)
{
MEMSET(visited, false);
int dirX[4]{ 1,-1,0,0 };
int dirY[4]{ 0,0,1,-1 };
queue<distInfo> distQueue;
distInfo first;
first.count = 0;
first.curPos = { x,y };
visited[COORD(first.curPos)] = true;
distQueue.push(first);
while (!distQueue.empty())
{
distInfo info = distQueue.front();
distQueue.pop();
for (int i = 0; i < 4; i++)
{
pair<int, int> dir = { dirX[i], dirY[i] };
distInfo tempInfo = info;
if (tempInfo.moveTo(map, dir))
{
visited[COORD(tempInfo.curPos)] = true;
char c = map[COORD(tempInfo.curPos)];
if (std::isdigit(c))
{
adj[node][c - '0'] = tempInfo.count;
}
distQueue.push(tempInfo);
}
}
}
}미리 map에 있는 로봇 청소기는 0으로, 먼지는 1~ 로 초기화 했으니 isdigit 함수를 통해서 먼지의 index를 구한 뒤 distInfo에 들어있는 이동 횟수를 넣어줍니다. 이렇게 보니까 조금 불안정하네요. 숫자 말고 알파벳으로 할걸 그랬습니다.
이렇게 인접 행렬을 완성 했다면 TSP를 돌려주면 됩니다. 모든 노드를 순회 후에 다시 시작점으로 돌아와야 하는 일반 TSP와 다르게 그냥 순회를 끝내면 되는거에요. dp와 재귀를 이용해서 풀어볼겁니다.
dp[currentNode][visited]를 currentNode에서 visited만큼의 노드를 순회했을때 남은 순회까지 남은 최소 비용이라고 하고 풀어봅시다.
여기서의 핵심은 visited에요. 대체 얘가 무엇이냐면 현재 노드에 도착하기 전에 들렸던 도시를 표기하는 정수입니다. 그리고 이러한 정수 하나에 어떠한 상태를 표기 하기 위해서 사용하는게 비트마스킹이죠.
대충 먼지가 5개 있다고 해봅시다. 먼지의 인덱싱은 0부터 진행합니다.
아직 그 무엇도 치우지 않았으니 모든 비트를 0으로 표기합니다.
그리고 이 상태에서 제가 3번째 먼지를 청소했다고 가정합시다.
그러면 이제 3번째 먼지를 마킹하면 돼요.
그리고 0번째랑 2번째 먼지도 청소했다고 해봅시다.
대충 감이 오시나요? 먼지를 청소한 상태에 따라 정수 값이 바뀌고 청소 상태가 같은게 아니면 정수 값이 겹칠 수 없죠.
이걸 2차원 배열의 Index로 쓰는겁니다.
비트 마스킹은 쉬프트 연산과 OR 연산을 잘 짬뽕하면 돼요. 한번 해봅시다.
노드를 순환할 때 최단 경로를 저장하기 위한 2차원 배열을 먼저 적습니다.
int dist[11][1 << 11];먼지는 최대 10개에 로봇 청소기 또한 노드이기 때문에 1을 11번 왼쪽으로 쉬프트를 해줍니다.
이러면 모든 비트가 1로 켜져도 IndexOutOfRange가 나지 않습니다.
그 뒤에 TSP 함수는 다음과 같이 적었습니다. 계산이 완료된 인접 행렬, 이동할 노드와 현재 이동한 노드 상태를 같이 매개변수로 넘겨줍니다.
int tsp(vector<vector<int>>& adj, int current, int visit)
먼저 모든 비트가 1이면 순회가 끝났다는것이니 0을 반환해줍니다.
int maxMask = (1 << dustCount) - 1;
if (visit == maxMask)
{
return 0;
}
그리고 만약 dist[current][visit]이 이미 계산되어있다면 그 계산 값을 반환합니다.
if (dist[current][visit] != -1)
return dist[current][visit];
그리고 이쪽이 핵심이에요. 일단 순회에 드는 가장 적은 코스트를 담을 변수를 선언하고 그냥 무진장 큰 값을 넣습니다.
그렇다고 진짜 무진장 크면 안됩니다. 오버플로우가 나진 않을정도로 적당히 큰 숫자로 넣어줍시다.
int minCost = VERY_BIG_NUMBER;
그리고 0번 노드를 제외한 모든 노드를 한번씩 순회할겁니다. 0번 노드를 제외하는건 0번이 시작점이기 때문에 이미 무조건 들린 상태라서 그래요.
for(int i = 1; i < dustCount; i++)
그리고 이 코드를 유심히 봐야합니다.
마킹된 채로 넘어온 visit을 검사하면서 현재 내가 이미 이동한 노드인지를 체크한 뒤에 인접 행렬을 뒤지면서 갈 수 있는 길이 있는지를 판단하는 코드입니다.
if ((visit & (1 << i)) == 0 && adj[current][i] != VERY_BIG_NUMBER)
만약 갈 수 있다면 재귀를 돌려주면 됩니다.
int toVisit = visit | (1 << i);
int tempCost = adj[current][i] + tsp(adj, i, toVisit);
minCost = std::min(tempCost, minCost);
그렇게 탐색이 끝이 나면 minCost에 적절한 값이 들어갈거고 그걸 dist[current][visit]에 넣어주고 반환해줄겁니다.
return dist[current][visit] = minCost;
만약 minCost가 여전히 VERY_BIG_NUMBER 라면 길이 없어 순회를 할 수 없었다는 뜻이니 순회가 불가능한 상황이란 뜻이겠죠.
그러니 이런식으로 solve 함수를 적어주면 됩니다.
MEMSET(dist, -1);
int cleanDist = tsp(adj, 0, 1);
if (cleanDist == VERY_BIG_NUMBER)
cout << -1 << '\n';
else
cout << cleanDist << '\n';
return true;
은근히 간단하죠?
마치는 말
솔직히 이거 먼지 갯수를 10개 상한이 아니라 한 20개로 뒀으면 외판원 순회가 강제돼서 플레 난이도 까지 올라갈 만한 문제인데 브루트포스가 돼서 골드 1인게 많이 아쉽습니다. 내 플레가!!!!
코드 전문
#define FAST_PRINT std::ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define BEGIN_TO_END(vec) vec.begin(), vec.end()
#define MEMSET(arr, i) memset(arr, i, sizeof(arr))
#define COORD(p) p.second][p.first
#define VERY_BIG_NUMBER 1e9
int w, h;
int dustCount;
bool visited[21][21];
int dist[11][1 << 11];
struct distInfo
{
int count;
pair<int, int> curPos;
bool moveTo(vector<vector<char>>& map, pair<int, int> dir)
{
curPos.first += dir.first;
curPos.second += dir.second;
if (isOutOfRange())
return false;
if (visited[COORD(curPos)])
return false;
if (map[COORD(curPos)] == 'x')
return false;
count++;
return true;
}
bool isOutOfRange()
{
return curPos.first < 0 || curPos.second < 0 || curPos.first >= w || curPos.second >= h;
}
};
void bfs(vector<vector<char>>& map, vector<vector<int>>& adj, int x, int y, int node)
{
MEMSET(visited, false);
int dirX[4]{ 1,-1,0,0 };
int dirY[4]{ 0,0,1,-1 };
queue<distInfo> distQueue;
distInfo first;
first.count = 0;
first.curPos = { x,y };
visited[COORD(first.curPos)] = true;
distQueue.push(first);
while (!distQueue.empty())
{
distInfo info = distQueue.front();
distQueue.pop();
for (int i = 0; i < 4; i++)
{
pair<int, int> dir = { dirX[i], dirY[i] };
distInfo tempInfo = info;
if (tempInfo.moveTo(map, dir))
{
visited[COORD(tempInfo.curPos)] = true;
char c = map[COORD(tempInfo.curPos)];
if (std::isdigit(c))
{
adj[node][c - '0'] = tempInfo.count;
}
distQueue.push(tempInfo);
}
}
}
}
int tsp(vector<vector<int>>& adj, int current, int visit)
{
int maxMask = (1 << dustCount) - 1;
if (visit == maxMask)
{
return 0;
}
if (dist[current][visit] != -1)
return dist[current][visit];
int minCost = VERY_BIG_NUMBER;
for(int i = 1; i < dustCount; i++)
{
if ((visit & (1 << i)) == 0 && adj[current][i] != VERY_BIG_NUMBER)
{
int toVisit = visit | (1 << i);
int tempCost = adj[current][i] + tsp(adj, i, toVisit);
minCost = std::min(tempCost, minCost);
}
}
return dist[current][visit] = minCost;
}
bool solve()
{
cin >> w >> h;
if (w == 0 || h == 0)
return false;
vector<vector<char>> map(h + 1, vector<char>(w + 1));
dustCount = 1;
pair<int, int> nodes[11];
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
cin >> map[i][j];
if (map[i][j] == '*')
{
map[i][j] = dustCount + '0';
nodes[dustCount++] = { j,i };
}
else if (map[i][j] == 'o')
{
map[i][j] = '0';
nodes[0] = { j,i };
}
}
}
vector<vector<int>> adj(dustCount + 1, vector<int>(dustCount + 1, VERY_BIG_NUMBER));
for (int i = 0; i <= dustCount; i++)
{
bfs(map, adj, nodes[i].first, nodes[i].second, i);
}
MEMSET(dist, -1);
int cleanDist = tsp(adj, 0, 1);
if (cleanDist == VERY_BIG_NUMBER)
cout << -1 << '\n';
else
cout << cleanDist << '\n';
return true;
}
int main()
{
FAST_PRINT;
while (solve());
}'알고리즘 > C++' 카테고리의 다른 글
| [백준] | C++ | 1557. 제곱 ㄴㄴ (포함-배제의 원리) (5) | 2025.04.29 |
|---|---|
| [백준] | C++ | 10942. 펠린드롬? (Top-down DP) (2) | 2025.04.20 |
| [백준] | C++ | 7453. 합이 0인 네 정수 (2) | 2025.04.11 |
| [백준] | C++ | 17626. Four Squares (0) | 2025.04.05 |
| [백준] | C++ | 2239. 스도쿠 (사진 설명 포함) (0) | 2024.12.27 |