기본적인 BFS문제입니다. 기존에는 4방향으로 이동하지만 6방향으로 이동한다는 차이점만 있습니다.
토마토 6방향문제와 동일한 문제입니다.
너무 일반적인 문제라 설명은 생략하겠습니다.
정답코드입니다.
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int l = 0, r = 0, c = 0;
int result;
char arr[31][31][31];
int visited[31][31][31];
int y_ar[6] = { 0, 0, 1, -1, 0, 0 };
int x_ar[6] = { 0, 0, 0, 0, 1, -1 };
int z_ar[6] = { 1, -1, 0, 0, 0, 0 };
void bfs(int sz,int sy,int sx) {
queue <int> que[3];
que[0].push(sz);
que[1].push(sy);
que[2].push(sx);
visited[sz][sy][sx] = 1;
while (que[0].empty() != 1) {
int zz = que[0].front();
int yy = que[1].front();
int xx = que[2].front();
que[0].pop(), que[1].pop(), que[2].pop();
for (int i = 0; i < 6; i++) {
int z = zz + z_ar[i];
int y = yy + y_ar[i];
int x = xx + x_ar[i];
if (z >= 0 && z < l && y >= 0 && y < r && x >= 0 && x < c)
if (visited[z][y][x] == 0 && arr[z][y][x] != '#') {
visited[z][y][x] = visited[zz][yy][xx] + 1;
que[0].push(z);
que[1].push(y);
que[2].push(x);
}
}
}
for (int i = 0; i < l; i++)
for (int j = 0; j < r; j++)
for (int k = 0; k < c; k++)
if (arr[i][j][k] == 'E')
result = visited[i][j][k];
}
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
while (1) {
cin >> l >> r >> c;
if (l == 0 && r == 0 && c == 0)
break;
memset(visited, 0, sizeof(visited));
result = (int)2e9;
int sz, sy, sx;
for (int i = 0; i < l; i++)
for (int j = 0; j < r; j++) {
cin >> arr[i][j];
for (int k = 0; k < c; k++) {
if (arr[i][j][k] == 'S')
sz = i, sy = j, sx = k;
}
}
bfs(sz, sy, sx);
if (result == 0)
cout << "Trapped!" <<"\n";
else
cout << "Escaped in " << result - 1<< " minute(s)." <<"\n";
}
return 0;
}
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int h = 0, w = 0;
int visited[1000][1000] = { 0 };
char arr[1000][1000];
queue <int> fire[2];
queue <int> people[2];
int x_ar[4] = { -1,1,0,0 };
int y_ar[4] = { 0,0,1,-1 };
void bfs() {
//초기값 입력
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
if (arr[i][j] == 'F')
fire[0].push(i), fire[1].push(j);
else if (arr[i][j] == 'J')
people[0].push(i), people[1].push(j), visited[i][j] = 1;
while (!people[0].empty()) { //상근이가 이동할 경로가 없을 때 까지 반복
//1. 불먼저 전파
int fire_cnt = fire[0].size();
while (fire_cnt--) {
int yy = fire[0].front();
int xx = fire[1].front();
fire[0].pop(), fire[1].pop();
for (int i = 0; i < 4; i++) {
int y = yy + y_ar[i];
int x = xx + x_ar[i];
if (y >= 0 && y < h && x >= 0 && x < w)
if (arr[y][x] == '.' || arr[y][x] == 'J') {
arr[y][x] = 'F';
fire[0].push(y), fire[1].push(x);
}
}
}
//2. 상근좌 이동
int people_cnt = people[0].size();
while (people_cnt--) {
int yy = people[0].front();
int xx = people[1].front();
people[0].pop(), people[1].pop();
for (int i = 0; i < 4; i++) {
int y = yy + y_ar[i];
int x = xx + x_ar[i];
if (y >= 0 && y < h && x >= 0 && x < w)
if (arr[y][x] == '.' && visited[y][x] == 0) {
visited[y][x] = visited[yy][xx] + 1;
people[0].push(y), people[1].push(x);
}
}
}
}
//3. 모서리의 visited값들을 확인하고 결과값을 도출
int result = 1000000;
bool alive = false;
for (int i = 0; i < h; i++) {
if (visited[i][0] != 0) {
alive = true;
if (visited[i][0] < result)
result = visited[i][0];
}
if (visited[i][w - 1] != 0) {
alive = true;
if (visited[i][w - 1] < result)
result = visited[i][w - 1];
}
}
for (int j = 0; j < w; j++) {
if (visited[0][j] != 0) {
alive = true;
if (visited[0][j] < result)
result = visited[0][j];
}
if (visited[h - 1][j] != 0) {
alive = true;
if (visited[h - 1][j] < result)
result = visited[h - 1][j];
}
}
if (alive)
cout << result << '\n';
else
cout << "IMPOSSIBLE" << '\n';
}
int main() {
cin >> h >> w;
for (int i = 0; i < h; i++) {
string val;
cin >> val;
for (int j = 0; j < val.size(); j++)
arr[i][j] = val[j];
}
bfs();
}
상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.
이라고 하기 때문에 불을 먼저 움직여주면 됩니다.
알고리즘은
1. 불먼저 전파
2. 상근좌 이동
1, 2번을 상근좌가 이동가능한 칸이 있을 때 까지 반복
3. 결과 값 도출
순입니다.
정답코드입니다.
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
using namespace std;
int t = 0, h = 0, w = 0;
int visited[1000][1000] = { 0 };
char arr[1000][1000];
queue <int> fire[2];
queue <int> people[2];
int x_ar[4] = { -1,1,0,0 };
int y_ar[4] = { 0,0,1,-1 };
void bfs() {
//초기값 입력
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
if (arr[i][j] == '*')
fire[0].push(i), fire[1].push(j);
else if(arr[i][j] == '@')
people[0].push(i), people[1].push(j), visited[i][j] = 1;
while (!people[0].empty()) { //상근이가 이동할 경로가 없을 때 까지 반복
//1. 불먼저 전파
int fire_cnt = fire[0].size();
while (fire_cnt--) {
int yy = fire[0].front();
int xx = fire[1].front();
fire[0].pop(), fire[1].pop();
for (int i = 0; i < 4; i++) {
int y = yy + y_ar[i];
int x = xx + x_ar[i];
if (y >= 0 && y < h && x >= 0 && x < w)
if (arr[y][x] == '.' || arr[y][x] == '@') {
arr[y][x] = '*';
fire[0].push(y), fire[1].push(x);
}
}
}
//2. 상근좌 이동
int people_cnt = people[0].size();
while (people_cnt--) {
int yy = people[0].front();
int xx = people[1].front();
people[0].pop(), people[1].pop();
for (int i = 0; i < 4; i++) {
int y = yy + y_ar[i];
int x = xx + x_ar[i];
if (y >= 0 && y < h && x >= 0 && x < w)
if (arr[y][x] == '.' && visited[y][x] == 0) {
visited[y][x] = visited[yy][xx] + 1;
people[0].push(y), people[1].push(x);
}
}
}
}
//3. 모서리의 visited값들을 확인하고 결과값을 도출
int result = 1000000;
bool alive = false;
for (int i = 0; i < h; i++) {
if (visited[i][0] != 0) {
alive = true;
if (visited[i][0] < result)
result = visited[i][0];
}
if (visited[i][w - 1] != 0) {
alive = true;
if (visited[i][w - 1] < result)
result = visited[i][w - 1];
}
}
for (int j = 0; j < w; j++) {
if (visited[0][j] != 0) {
alive = true;
if (visited[0][j] < result)
result = visited[0][j];
}
if (visited[h - 1][j] != 0) {
alive = true;
if (visited[h - 1][j] < result)
result = visited[h - 1][j];
}
}
if (alive)
cout << result << '\n';
else
cout << "IMPOSSIBLE" << '\n';
}
int main() {
cin >> t;
while (t--) {
memset(visited, 0, sizeof(visited));
while (!fire[0].empty())
fire[0].pop(), fire[1].pop();
cin >> w >> h;
for (int i = 0; i < h; i++) {
string val;
cin >> val;
for (int j = 0; j < val.size(); j++)
arr[i][j] = val[j];
}
bfs();
}
}
전형적인 bfs 문제입니다. d(p1,p2)=|i1-i2|+|j1-j2| 을 만족하는 최단 경로 탐색문제입니다.
너무 쉬워서 설명은 생략하겠습니다.
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int n = 0, m = 0;
int arr[183][183] = { 0 };
int visited[183][183] = { 0 };
int que[40000][2] = { 0 };
int started = 0, ended = 0;
int x_go[4] = { 0,0,1,-1 };
int y_go[4] = { 1,-1,0,0 };
void bfs() {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (arr[i][j] == 1)
que[ended][0] = i, que[ended++][1] = j, visited[i][j] = 1;
while (started != ended) {
int y = que[started][0];
int x = que[started++][1];
for (int i = 0; i < 4; i++) {
int yyy = y + y_go[i];
int xxx = x + x_go[i];
if (yyy >= 0 && yyy < n && xxx >= 0 && xxx < m)
if (!visited[yyy][xxx]) {
visited[yyy][xxx] = visited[y][x] + 1;
que[ended][0] = yyy, que[ended++][1] = xxx;
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
string arg;
cin >> arg;
for (int j = 0; j < m; j++) {
arr[i][j] = arg[j] - '0';
}
}
bfs();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << visited[i][j] - 1 << ' ';
cout << '\n';
}
}
그리고 조금더 오래걸리지만 브루트포스의 형식으로도 solve를 받을 수 있습니다.
장점: 쉬운 문제풀이 단점: 시간
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int n = 0, m = 0;
int arr[183][183] = { 0 };
int visited[183][183] = { 0, };
int que[40000][2] = { 0 };
int ended = 0;
void func() {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (arr[i][j] == 1)
que[ended][0] = i, que[ended++][1] = j;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
int y = i, x = j;
for (int k = 0; k < ended; k++) {
if (arr[y][x] == 0) {
int val = abs(y - que[k][0]) + abs(x - que[k][1]);
if (visited[y][x] > val) {
visited[y][x] = val;
}
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
string arg;
cin >> arg;
for (int j = 0; j < m; j++) {
arr[i][j] = arg[j] - '0';
if (arr[i][j] == 0)
visited[i][j] = 1000;
}
}
func();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << visited[i][j] << ' ';
cout << '\n';
}
}
당연히 탐색이라면 dfs, bfs를 먼저 생각하셔야 합니다. 문제 조건으로 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)입니다. 비교적 큰 수이기 때문에 dfs보다는 bfs를 먼저 생각했습니다.
각각의 n번에서 최적탐색을 통해서 가장 빨리 도달하는 관계의 합을 더해주면 되는 방식이였습니다.
정답코드입니다. bfs코드이고 4ms 정도의 시간이 걸립니다. 풀면서도 살짝 긴가민가 했습니다.
왜냐하면 O(n*m*n*큐)이고 대략 50,000,000 이상의 반복연산을 하기때문입니다. 1억번에는 훨씬 못미치지만 반복을 재외한 큐이므로 큐자체도 100번은 반복하지 않을까하는 생각때문입니다.
다행히 문제는 통과했습니다. ( 1초에 1억번이라는게 정확한 연산은 아니기도 하고 큐에 대해서 제가 놓치고 있는 부분이 있기에 통과된것같습니다.)
#include <iostream>
#include <cstring>
using namespace std;
int n = 0, m = 0;
int arr[5001][2];
int visited[5001];
int result = 1000000000,result_index =-1;
int bfs(int num) {
int val = 0;
int que[5000];
for (int i = 1; i <= n; i++) {
if (num == i) continue;
memset(que, 0, 5000);
memset(visited, 0, 5001);
int started = 0, ended = 0;
que[ended++] = num;
visited[num] = 1;
while (ended != started) {
int a = que[started++];
if (a == i) {
val += visited[a] - 1;
break;
}
for (int j = 0; j < m; j++) {
if (arr[j][0] == a && !visited[arr[j][1]]) {
que[ended++] = arr[j][1];
visited[arr[j][1]] = visited[a] + 1;
}
else if (arr[j][1] == a && !visited[arr[j][0]]) {
que[ended++] = arr[j][0];
visited[arr[j][0]] = visited[a] + 1;
}
}
}
}
return val;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> arr[i][0] >> arr[i][1];
for (int i = 1; i <= n; i++) { //1~n번까지의 경로를 탐색
int val = bfs(i);
if (result > val) result = val, result_index = i;
}
cout << result_index << endl;
}
근데 생각해보니 더욱 효율적인 방법이 있었습니다.
굳이 bfs문에서 n번 반복해줄 필요가 없었습니다...
어차피 while문이 한번다 돌고나면 visited엔 모든 인덱스별 최단경로값이 들어가있게 됩니다.
친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.
이 문제조건 때문입니다.
수정코드입니다.
시간도 0ms로 줄었습니다.
#include <iostream>
#include <cstring>
using namespace std;
int n = 0, m = 0;
int arr[5001][2];
int visited[5001];
int result = 1000000000,result_index =-1;
int bfs(int num) {
int val = 0;
int que[5000];
memset(que, 0, 5000);
memset(visited, 0, 5001);
int started = 0, ended = 0;
que[ended++] = num;
visited[num] = 1;
while (ended != started) {
int a = que[started++];
for (int j = 0; j < m; j++) {
if (arr[j][0] == a && !visited[arr[j][1]]) {
que[ended++] = arr[j][1];
visited[arr[j][1]] = visited[a] + 1;
}
else if (arr[j][1] == a && !visited[arr[j][0]]) {
que[ended++] = arr[j][0];
visited[arr[j][0]] = visited[a] + 1;
}
}
}
for (int i = 1; i <= n; i++)
val += visited[i] - 1;
return val;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> arr[i][0] >> arr[i][1];
for (int i = 1; i <= n; i++) { //1~n번까지의 경로를 탐색
int val = bfs(i);
if (result > val) result = val, result_index = i;
}
cout << result_index << endl;
}
dfs코드입니다. 다른 분의 코드를 참고해서 만들었습니다. 216ms로 시간이 오래걸립니다. 어느 것이 더욱 좋다 이 것보다는 자기한테 편한코드로 ac를 받으면 되는거라고 생각합니다. dfs의 장점은 명료하고 직관적이라는 것입니다. 다음뻔에는 dfs로 풀어야하는 문제를 리뷰하겠습니다. 모두 화이팅 :)
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 102
#define INF 987654321
using namespace std;
int n,m;
int a,b;
int ans,res,step;
int person;
bool check[MAX];
vector<int> v[MAX];
void dfs(int ind,int goal,int cnt){
if(ind == goal){
step = min(step,cnt);
return;
}
for(int i=0; i<v[ind].size(); i++){
if(!check[v[ind][i]]){
check[ind] = true;
dfs(v[ind][i],goal,cnt+1);
check[ind] = false;
}
}
}
int main(int argc, const char * argv[]) {
// cin,cout 속도향상
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// 입력
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
// 탐색
ans = INF;
for(int i=1; i<=n; i++){
memset(check, false, sizeof(check));
res = 0;
for(int j=1; j<=n; j++){
step = INF;
if(i==j) continue;
else{
dfs(i,j,0);
res += step;
}
}
// 최소인지 검사
if(ans > res){
ans = res;
person = i;
}else if(ans == res){
person = min(person, i);
}
}
cout << person << endl;
}
처음에 가진 생각은 가장 이동경로내에 여러개의 편의점이 있으면 어디를 선택할까와 같은 생각을 했지만, 다시 생각해보니 무의미했습니다. yes, no로 도달할 수 있는지만 판단하면 되었기 때문입니다. 그렇기 때문에 모든 편의점을 탐색하며 도달할 수 있는지 여부만 판단했습니다.
bfs알고리즘을 사용해서 방문여부를 판단했습니다.
주의 하셔야 할 점은 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리) 입니다.
문제를 꼼꼼히 읽는 습관을 가져야 합니다.
아래는 정답코드입니다.
#include <iostream>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std;
int t = 0, n = 0;
int arr[101][2] = { 0 };
int starting_x, starting_y, destination_x, destination_y;
bool visited[101];
int que[1000000][2] = { 0 };
int started = 0, ended = 0;
void bfs() {
que[ended][0] = starting_y;
que[ended++][1] = starting_x;
while (started != ended) {
int y = que[started][0];
int x = que[started++][1];
for (int i = 0; i <= n; i++) {
if (!visited[i]) {
int len_x = min(abs(x - arr[i][1]), abs(arr[i][1] - x));
int len_y = min(abs(y - arr[i][0]), abs(arr[i][0] - y));
double len_total = len_x + len_y;
if (len_total <= 1000)
{
visited[i] = 1;
que[ended][0] = arr[i][0];
que[ended++][1] = arr[i][1];
}
}
}
}
}
int main() {
cin >> t;
while (t--) {
cin >> n;
cin >> starting_x >> starting_y;
for (int i = 0; i < n; i++)
cin >> arr[i][1] >> arr[i][0];
cin >> arr[n][1] >> arr[n][0];
memset(visited, 0, sizeof(visited));
started = 0, ended = 0;
bfs();
if (visited[n])
cout << "happy" << endl;
else
cout << "sad" << endl;
}
}