https://www.acmicpc.net/problem/5022
총 BFS를 4번 돌려서 해결했습니다.(a먼저 선 긋고 b선, b먼저 선 긋고 a) 각각 선마다 다 BFS
a를 먼저 긋는 경우와 b를 먼저 긋는 경우에 따라 결과 값은 물론 못 긋는 선의 유무도 다르기 때문에
무조건 순서를 바꿔서도 돌려줘야합니다.
저는 구조체에 좌표와 vecotr를 사용한 경로를 저장해줬고, 해당 구조체를 큐로 하여 BFS를 돌렸습니다.
이 때 당연히 다른 점의 좌표들은 건들여선 안되고, 만약 두번째 긋는 선이면 첫번째 그은 선을 건들여선 안됩니다.
이렇게 구한 값들을 가지고 결과값을 잘 출력한다면 결과값이 나올 것입니다.
계속 틀리는 분은 십자가로 입력을 한번 줘보시고,
check(또는 visit)배열을 출력해봐서 어떻게 그림이 나오는지 확인해보세요
또한 x,y,n,m의 입력을 거꾸로 사용하진 않았는지,
여기선 n+1, m+1까지 탐색해야하는데 이렇게 하진 않지 않았는지 확인해보세요
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
bool visit[101][101];
struct Info {
int x;
int y;
vector <pair<int, int>> path;//경로저장
};
queue <Info> q[2];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int bfs(int ax0, int ay0, int ax1, int ay1, int bx0, int by0, int bx1, int by1, int index) {
while (!q[index].empty()) q[index].pop();//큐 정리 후 시작
vector <pair<int, int>> v;
v.push_back(make_pair(ax0, ay0));
bool ch[101][101] = { 0, };
if (index == 1) {//두번째출발이면 첫번째에서 얻은 경로를 ch에 저장
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
ch[i][j] = visit[i][j];
}
q[index].push({ ax0,ay0,v });
ch[ax0][ay0] = true;
while (!q[index].empty()) {//bfs ㄱㄱ
int x = q[index].front().x;
int y = q[index].front().y;
vector < pair<int, int>> path = q[index].front().path;
if (x == ax1 && y == ay1) {//도착지에 도착
int size = path.size();
if (index == 0) {//첫번째출발이면
for (int a = 0; a < size; a++) {//배열에 경로저장
int px = path[a].first;
int py = path[a].second;
visit[px][py] = true;
}
}
return size - 1;//벡터크기의 -1이 선의 길이
}
q[index].pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx <= n && ny <= m && ch[nx][ny] == false) {
//다른 점만나면 바로 continue
if ((nx == bx0 && ny == by0) || (nx == bx1 && ny == by1)) continue;
ch[nx][ny] = true;
path.push_back(make_pair(nx, ny));
q[index].push({ nx,ny,path });//좌표와 경로를 큐에 저장
path.pop_back();
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
int ax0, ay0, ax1, ay1, bx0, by0, bx1, by1;
cin >> ay0 >> ax0 >> ay1 >> ax1 >> by0 >> bx0 >> by1 >> bx1;
//a부터 먼저 출발~
int alen0 = bfs(ax0, ay0, ax1, ay1, bx0, by0, bx1, by1, 0);
int blen0 = bfs(bx0, by0, bx1, by1, ax0, ay0, ax1, ay1, 1);
int sum0 = alen0 + blen0;
for (int i = 0; i <= n; i++) //앞에서 썻던 경로배열 다시 초기화
for (int j = 0; j <= m; j++)
visit[i][j] = false;
//b부터 출발~
int blen1 = bfs(bx0, by0, bx1, by1, ax0, ay0, ax1, ay1, 0);
int alen1 = bfs(ax0, ay0, ax1, ay1, bx0, by0, bx1, by1, 1);
int sum1 = alen1 + blen1;
int sum2 = sum0 <= sum1 ? sum0 : sum1;
//결과출력
if ((alen0 == -1 || blen0 == -1) && (alen1 == -1 || blen1 == -1))
cout << "IMPOSSIBLE";
else if (alen0 == -1 || blen0 == -1) cout << sum1;
else if (alen1 == -1 || blen1 == -1) cout << sum0;
else cout << sum2;
}
- 나 혼자 말하고 나 혼자 듣는 말
….. 알고리즘 인생 중 제일 어려웠다…. 후… 아니 테스트케이스가 하나 밖에 없으니까 찾기도 힘들고
설마 bfs 4번이나 돌려야 됐을 줄이야… 후…
뭐 이 문제 덕분에 큐에 벡터 경로 집어 넣고 하는 방법은 처음이었어서 도움은 되었다.
빡치긴 했던 문제지만 그 만큼 얻은 것도 많았던 문제
다신 풀고 싶지 않다 후…