#include <iostream>
#include <queue>
#include <map>
using namespace std;
int n;
int dy[6] = { -2, -2, 0, 0, 2, 2 };
int dx[6] = { -1, 1, -1, 2, -1, 1 };
map<pair<int, int>, int> dist;
/*
O X O X O
O O O O O
X O X O X
O O O O O
O X O X O
*/
bool isOut(int y, int x) {
return (y < 0 || y >= n || x < 0 || x >= n);
}
int main() {
cin >> n;
pair<int, int> p1, p2;
cin >> p1.first >> p1.second >> p2.first >> p2.second;
queue<pair<int, int>> q;
q.push(p1);
dist.insert({ p1, 0 });
while (!q.empty()) {
pair<int, int> here = q.front(); q.pop();
for (int direction = 0; direction < 6; direction++) {
pair<int, int> there = make_pair(here.first + dy[direction], here.second + dx[direction]);
if (isOut(there.first, there.second)) continue;
if (there.first == p2.first && there.second == p2.second)
break;
// there을 방문하지 않았다면
if (dist.find(there) == dist.end()) {
dist[there] = dist[here] + 1;
q.push(there);
}
}
}
if (dist.find(p2) != dist.end())
cout << dist[p2] << endl;
else
cout << -1 << endl;
return 0;
}
해설
모든 정점을 다 방문했을 때 N^2의 시간 복잡도를 가진다.
#include <iostream>
#include <queue>
#include <map>
using namespace std;
int n;
int dy[6] = { -2, -2, 0, 0, 2, 2 };
int dx[6] = { -1, 1, -2, 2, -1, 1 };
int dist[200][200];
/*
O X O X O
O O O O O
X O X O X
O O O O O
O X O X O
*/
bool isOut(int y, int x) {
return (y < 0 || y >= n || x < 0 || x >= n);
}
int main() {
cin >> n;
pair<int, int> p1, p2;
cin >> p1.first >> p1.second >> p2.first >> p2.second;
memset(dist, -1, sizeof(dist));
queue<pair<int, int>> q;
q.push(p1);
dist[p1.first][p1.second] = 0;
while (!q.empty()) {
pair<int, int> here = q.front(); q.pop();
for (int direction = 0; direction < 6; direction++) {
pair<int, int> there = make_pair(here.first + dy[direction], here.second + dx[direction]);
if (isOut(there.first, there.second)) continue;
// there을 방문하지 않았다면
if(dist[there.first][there.second] == -1){
dist[there.first][there.second] = dist[here.first][here.second] + 1;
q.push(there);
}
}
}
int ret = dist[p2.first][p2.second];
if (ret == -1)
cout << -1 << endl;
else
cout << ret << endl;
return 0;
}
피드백 : 두 점에 대한 dist를 저장해야하는 경우에는 이차원 배열을 사용한다. 그리고 there = p2가 되었을 때 그 아래에 있는 요 조건문을 통과해야 dist[p2.first][p2.second]의 값이 채워진다. 무작정 break한 나 자신 반성해
#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <string.h>
using namespace std;
bool check[10000];
int dist[10000]; // dist[i] : 시작점부터 i까지 오는 거리
int from[10000]; // from[i] : i 값을 구하기 직전의 숫자
char how[10000]; // how[i] : from[i]에서 i 숫자를 구하기 위해 D, S, L, R 중 어떤 명령어를 사용했는지
char comm[4] = { 'D', 'S','L', 'R' };
int transform(int flag, int n) {
if (flag == 0) // D
return (n * 2) % 10000;
else if (flag == 1) { // S
if (n == 0) return 9999;
return n - 1;
}
else if (flag == 2) // L
return (n % 1000) * 10 + n / 1000;
else if (flag == 3) // R
return (n / 10) + (n % 10) * 1000;
else return -1;
}
int main() {
int cases; cin >> cases;
while (cases--) {
int a, b; cin >> a >> b;
memset(check, false, sizeof(check));
memset(dist, 0, sizeof(dist));
memset(from, 0, sizeof(from));
memset(how, '\\0', sizeof(how));
queue<int> q;
q.push(a);
// 시작 정점 세팅
check[a] = true;
dist[a] = 0;
from[a] = -1;
while (!q.empty()) {
int here = q.front(); q.pop();
for (int command = 0; command < 4; command++) {
int there = transform(command, here);
if (check[there] == false) {
q.push(there);
dist[there] = dist[here] + 1;
from[there] = here;
how[there] = comm[command];
check[there] = true;
}
}
}
string ret = "";
while (b != a) {
ret += how[b];
b = from[b];
}
/*
int prev = from[b];
string ret = "";
ret += how[b];
while (prev != a) {
ret += how[prev];
prev = from[prev];
}
*/
reverse(ret.begin(), ret.end());
cout << ret << endl;
}d
return 0;
}
D S L R 중에 하나를 골라서 반복한다.
간과한 점
#include <iostream>
#include <queue>
using namespace std;
int board[9][9];
int n, m;
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { -1, 1, 0, 0 };
bool isOut(pair<int, int>& p) {
int y = p.first, x = p.second;
return (y < 0 || y >= n || x < 0 || x >= m);
}
int bfs() {
queue<pair<int, int>> q;
int info[9][9];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++){
info[i][j] = board[i][j];
if (info[i][j] == 2) q.push(make_pair(i, j));
}
// BFS로 바이러스가 퍼진 영역의 개수를 구한다.
while (!q.empty()) {
pair<int, int> here = q.front(); q.pop();
for (int direction = 0; direction < 4; direction++) {
pair<int, int> there = make_pair(here.first + dy[direction], here.second + dx[direction]);
// 다음 칸이 빈칸이면 바이러스가 전염된다.
if (!isOut(there)) {
if(info[there.first][there.second] == 0){
q.push(there);
info[there.first][there.second] = 2;
}
}
}
}
int cnt = 0; // 안전 영역의 수 계산
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (info[i][j] == 0) cnt++;
return cnt;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> board[i][j];
int ret = 0;
// 세 개의 벽을 세우는 모든 경우를 탐색한다.
for(int y1 = 0; y1 < n; y1++)
for (int x1 = 0; x1 < m; x1++) {
if (board[y1][x1] != 0) continue; // 빈 칸이 아니면 패스
for(int y2 = 0; y2 < n; y2++)
for (int x2 = 0; x2 < m; x2++) {
if (board[y2][x2] != 0) continue;
for(int y3 = 0; y3 < n; y3++)
for (int x3 = 0; x3 < m; x3++) {
if (board[y3][x3] != 0) continue;
if (y1 == y2 && x1 == x2) continue;
if (y1 == y3 && x1 == x3) continue;
if (y2 == y3 && x2 == x3) continue;
board[y1][x1] = 1;
board[y2][x2] = 1;
board[y3][x3] = 1;
int cand = bfs();
if (ret < cand) ret = cand;
board[y1][x1] = 0;
board[y2][x2] = 0;
board[y3][x3] = 0;
}
}
}
cout << ret << endl;
return 0;
}
(0) 안전 영역이 최대가 되도록 3개의 벽을 세우는 것 (1) 바이러스가 퍼지고 벽에 가로막히면 더 이상 퍼지지 않는 것 (2) 안전 영역의 크기를 계산하는 것 (BFS)