1. 1525 - BFS / SET
https://www.acmicpc.net/problem/1525
많이 해본 퍼즐이긴한데.. 공식은 모르고 그냥 움직여만 봤다
각 숫자가 본인의 자리에 있으면 성공인것인데..
최단거리를 어떻게 구해야할까..?
우선 최단거리니까 BFS를 사용할 것이다.
그런데 이게 한 점을 목표로 옮기면, 다른 점이 망가지는데..
어떻게 해야하지..
이런 순서로 이동이 되는 셈인데..
큐에 먼저 본인 자리에 없는 것들부터 집어넣을까?
아예 구현법이 생각이 나지 않아서
8 Puzzle의 BFS 구현에 대해 검색해보았고,
위의 그래프를 얻게 되었다.
그래프만 보고서, 이 문제는 기존의 BFS와 다르다고 생각했다.
여태까지 큐에 좌표만 넣었었고, 지금 문제는 빈칸의 좌표를
넣으려고 했었는데, 그렇게 하면 안될 것 같다.
map 자체를 넘겨야할 것 같다.
map 상태 자체가 하나의 노드가 되는 것이다.
다시 방문하면 안되는 하나의 visited가 되는 것이다.
실마리가 80%는 풀린 것 같다. 구현해본다.
시도
위처럼 string[3]이라는 맵의 상태를
vector로 담고 싶었는데, 오류가 났다.
그래서 string하나로 구현해보기로 했다.
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int d[4] = {-3, 3, -1, 1}; // 4방향
vector<string> visitedStage; // visited
string clearStage = "123456780";
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string start;
// 입력
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
char num;
cin >> num;
start.push_back(num);
}
}
queue<pair<string, int>> nextStage;
// visited 이후 push
visitedStage.push_back(start);
nextStage.push({start, 0});
while (!nextStage.empty())
{
string thisStage = nextStage.front().first;
int count = nextStage.front().second;
nextStage.pop();
int zeroIndex;
// 정렬된 상태에 도달한다면, 종료
if (thisStage == clearStage)
{
cout << count;
return 0;
}
// 0의 인덱스를 찾음
for (int i = 0; i < 9; i++)
{
if (thisStage[i] == '0')
{
zeroIndex = i;
}
}
// 0의 위치로부터 4방향을 봄, 갈 수 있다면 간다.
// (+visited로 같은 상태가 아니면)
for (int i = 0; i < 4; i++)
{
int c = zeroIndex + d[i];
if (c < 0 || c >= 9) // 위아래
{
continue;
}
else if (((zeroIndex + 1) % 3 == 1) && i == 2) // 왼쪽벽인데 왼쪽으로
{
continue;
}
else if (((zeroIndex + 1) % 3 == 0) && i == 3)
{
continue;
}
else
{
string tmpStage = thisStage;
char tmp;
tmp = tmpStage[c]; // 갈 수 있는 곳을 저장
tmpStage[c] = '0'; // 갈 수 있는 곳을 실제로 감
tmpStage[zeroIndex] = tmp; // 서로 값을 바꾸는 것
// 그러면 지금 tmpStage는 실제로 이동한 상태
// 해당 상태가 벡터에 없는 처음보는 상태인지 전 벡터 순회
bool existStage = false;
for (int n = 0; n < visitedStage.size(); n++)
{
if (visitedStage[n] == tmpStage)
{
existStage = true;
}
}
// 처음보는 상태가 맞다면, 방문추가 및 큐에추가
if (!existStage)
{
visitedStage.push_back(tmpStage);
nextStage.push({tmpStage, count + 1});
}
}
}
}
cout << -1;
return 0;
}
시간초과가 났다.
아무래도 visited라는 벡터의 모든 원소들을 비교한게
부하가 심한 것 같은데..
다른 구현법이 있을까..
현재 상태를 저장하고 각각 비교하는건 반드시 해야할텐데..
해결
https://codingwell.tistory.com/57
Vector가 아니라,
Set을 사용하면 중복을 없애는 자료구조적 성질때문에
더 쉽게 구현할 수가 있다고 한다.
오..
#include <iostream>
#include <queue>
#include <set>
#include <cstring>
using namespace std;
int d[4] = {-3, 3, -1, 1}; // 4방향
set<string> visitedStage; // visited
string clearStage = "123456780";
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
string start;
// 입력
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
char num;
cin >> num;
start.push_back(num);
}
}
queue<pair<string, int>> nextStage;
// visited 이후 push
visitedStage.insert(start);
nextStage.push({start, 0});
while (!nextStage.empty())
{
string thisStage = nextStage.front().first;
int count = nextStage.front().second;
nextStage.pop();
int zeroIndex;
// 정렬된 상태에 도달한다면, 종료
if (thisStage == clearStage)
{
cout << count;
return 0;
}
// 0의 인덱스를 찾음
for (int i = 0; i < 9; i++)
{
if (thisStage[i] == '0')
{
zeroIndex = i;
}
}
// 0의 위치로부터 4방향을 봄, 갈 수 있다면 간다.
// (+visited로 같은 상태가 아니면)
for (int i = 0; i < 4; i++)
{
int c = zeroIndex + d[i];
if (c < 0 || c >= 9) // 위아래
{
continue;
}
else if (((zeroIndex + 1) % 3 == 1) && i == 2) // 왼쪽벽인데 왼쪽으로
{
continue;
}
else if (((zeroIndex + 1) % 3 == 0) && i == 3)
{
continue;
}
else
{
string tmpStage = thisStage;
char tmp;
tmp = tmpStage[c]; // 갈 수 있는 곳을 저장
tmpStage[c] = '0'; // 갈 수 있는 곳을 실제로 감
tmpStage[zeroIndex] = tmp; // 서로 값을 바꾸는 것
// 그러면 지금 tmpStage는 실제로 이동한 상태
// set의 find는 해당 원소가 없을시, end를 반환함
if (visitedStage.find(tmpStage) == visitedStage.end())
{
visitedStage.insert(tmpStage);
nextStage.push({tmpStage, count + 1});
}
}
}
}
cout << -1;
return 0;
}
해당 부분을 바꾸었다. 더 간략해졌다.
풀이
https://blockdmask.tistory.com/79
set 자료구조는
- insert시 원소가 오름차순으로 정렬 (중위순회로 순서대로 출력가능)
- 생성시에 정렬기준을 바꿀 수도 있음
- begin / end로 처음과 끝을 접근할 수 있음 (iterator)
- insert로 삽입이 실패시 pair_bool 값을 반환
- find로 찾는것이 실패시, end를 반환
그러니까 SET을 사용하는 이유는,
- 중복데이터제거 / 값 빠르게 찾기
BFS로 현실에서도 못푸는 8Puzzle을 풀었다..
모든 경우의 수를 방문하고 답에 도달하면 종료하는 방식인건데
해당 조건을 어떻게 주느냐,
상황을 기록할 자료구조는 어떻게 하는가에 따라 응용이 무궁무진한 것 같다.
2. 2206 - BFS
https://www.acmicpc.net/problem/2206
말 문제의 하위호환 문제로 보인다.
해결
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
bool visited[1000][1000][2]; // 마지막은 벽을 부시는 능력을 썼는지
int map[1000][1000];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int map_X, map_Y;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> map_X >> map_Y;
memset(visited, false, sizeof(visited));
memset(map, 0, sizeof(map));
string s;
for (int i = 0; i < map_X; i++)
{
cin >> s;
for (int j = 0; j < map_Y; j++)
{
map[i][j] = s[j] - '0';
}
}
queue<pair<pair<int, int>, pair<int, int>>> nextNode;
visited[0][0][1] = true;
nextNode.push({{0, 0}, {1, 1}});
while (!nextNode.empty())
{
int x = nextNode.front().first.first;
int y = nextNode.front().first.second;
int count = nextNode.front().second.first;
int remainAbility = nextNode.front().second.second;
nextNode.pop();
/*
cout << "\n\n[thisNode]\n";
cout << "x : " << x << "\n";
cout << "y : " << y << "\n";
cout << "count : " << count << "\n";
cout << "remain : " << remainAbility << "\n";
*/
if (x == map_X - 1 && y == map_Y - 1)
{
cout << count;
return 0;
}
for (int i = 0; i < 4; i++)
{
int cx = x + dx[i];
int cy = y + dy[i];
if (cx < 0 || cx >= map_X || cy < 0 || cy >= map_Y)
{
continue;
}
else
{
if (map[cx][cy] == 0)
{
if (!visited[cx][cy][remainAbility])
{
visited[cx][cy][remainAbility] = true;
nextNode.push({{cx, cy}, {count + 1, remainAbility}});
}
}
else if (map[cx][cy] == 1)
{
if (remainAbility > 0)
{
visited[cx][cy][remainAbility - 1] = true;
nextNode.push({{cx, cy}, {count + 1, remainAbility - 1}});
}
}
}
}
}
cout << -1;
return 0;
}풀이
어렵지 않은 문제였다.
하지만 실수하기 좋은 문제였다.
입력이 위와 같아서 문자열로 받고, 다시 문자로 나눠서 저장해야했다.
무조건 - '0'을 해줘야만 정상적으로 정수가 들어가게 된다.
그 외에는 x와 y를 순서대로 사용하고 싶어서
입력에서 x에 실제y값을 받고 y에 실제x값을 받았는데,
조건에서 정확히 사용하기 위해 인지해두어야한다.
DFS와 BFS는 4일만에 골드 2까지 무리없이 이해하고 푸는데 도달했다.
(골드 1문제가 따로 없음)
