https://www.acmicpc.net/problem/1707


가령 1--2--3--4 


이러한 연결 관계를 가지는 그래프가 주어지면, 1을 빨간색, 2를 초록색으로 칠하고, 다시 3을 빨간색 4를 초록색


이렇게 두 가지의 색을 이용하여, 그래프의 모든 노드를 인접한 노드의 삭과 다른 색으로 색칠 할 수 있는지


검증하는 문제이다.



색깔의 구현은, 방문 처리 배열의 값을 1과 2사이에서 토글되게 하였다. 0이면 방문하지 않은것



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#pragma warning(disable :4996)
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
vector<int> grp[20001];
 
int vis[20001]; //초기 0, 두종류 1,2 -> 인접한 정점간에 다른 vis 값을 가지면 이분그래프
int vCnt, eCnt;
bool isBigrp = true;
queue<int> q;
void bfs(int st) {
    q.push(st);
    vis[st] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < grp[cur].size(); i++) {
            
            int next = grp[cur][i]; //확인할 지점
            
            if (vis[next] != 0 && vis[cur] == vis[next]) { //인접한 정점과 같은 vis값을 가지는 경우
                cout << "NO\n";
                isBigrp = false;
                return;
            }
            if (vis[next] > 0continue//재방문 못하게
            q.push(next);
            vis[next] = vis[cur] % 2 + 1//cur이 1이면 next는 2가되고, vice versa
            
        }
    }
    
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> vCnt >> eCnt;
        for (int i = 0; i < eCnt; i++) {
            int src, dst;
            cin >> src >> dst;
            grp[src].push_back(dst);
            grp[dst].push_back(src);
        }
        
        for (int i = 1; i <= vCnt; i++) {
            if (vis[i] == 0) {
                bfs(i);
                if (!isBigrp) break// 이분그래프가 아니라는 결론이 났으면 더 진행할 필요가 없다
            }
        }
        if(isBigrp)
            cout << "YES\n";
 
        //이 아래로는 초기화 부분
        while (!q.empty()) q.pop();
        for (int i = 1; i <= vCnt; i++) {
            vis[i] = 0;
            grp[i].clear();
        }
        isBigrp = true;
    }
    return 0;
}
 
cs


https://www.acmicpc.net/problem/1389


정점별로 연걸된 나머지 정점까지의 거리의 합을 구하고, 그 합의 최솟값을 가지는 정점의 번호를 출력해주면 된다.



인접행렬을 만들 때, 방향성이 없는 그래프라는 것을 주의하자.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
 
int grp[101][101]; // 1-indexed
int n, m; //유저수, 관계수
int dis[101]; //방문처리 + 거리
queue<int> q;
 
void bfs(int st) {
    q.push(st);
    dis[st]++;
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            int cur = q.front();
            q.pop();
            for (int i = 1; i <= n; i++) {
                if (grp[cur][i] != 1 || dis[i] >= 0continue;
                q.push(i);
                dis[i] = dis[cur] + 1;
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int src, dst;
        cin >> src >> dst;
        grp[src][dst] = 1;
        grp[dst][src] = 1//무방향성
    }
 
    int Min = 100000000, ans;
    for (int i = 1; i <= n; i++) {
        for (int i = 1; i <= n; i++//방문처리 배열 초기화
            dis[i] = -1;
        bfs(i);
        int Sum = 0;
        for (int i = 1; i <= n; i++)
            Sum += dis[i];
        if (Sum < Min) {
            Min = Sum;
            ans = i;
        }
    }
    cout << ans;
    
    return 0;
}
 
cs


https://www.acmicpc.net/problem/2644


특정 노드 사이의 촌수를 계산해주면 된다.



주어지는 정보들을 그래프로 표현해보면, 결국 촌수는 정점과 정점사이의 최단거리이다.



따라서 BFS를 활용하여 구현한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
 
int grp[101][101]; //1-indexed
int vis[101]; //양수면 방문한 것
queue<int> q;
 
int n, st, en, m; //n명의 사람, m개의 관계
 
void bfs() {
    q.push(st);
    vis[st]++;
    
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            int cur = q.front();
            q.pop();
            for (int i = 1; i <= n; i++) {
                if (grp[cur][i] != 1 || vis[i] >= 0continue;
                
                q.push(i);
                vis[i] = vis[cur] + 1;
                if (i == en) { //종료 조건
                    cout << vis[i];
                    return;
                }
            }
        }
    }
    cout << -1// 연결이 되지 않은 것
}
 
int main(void) {
 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> st >> en >> m;
    for (int i = 1; i <= m; i++) {
        int src, dst;
        cin >> src >> dst;
        grp[src][dst] = 1;
        grp[dst][src] = 1//무방향성
    }
 
    for (int i = 1; i <= n; i++)
        vis[i] = -1//양수면 방문한 것으로 처리
 
    bfs();
 
    return 0;
}
 
cs


https://www.acmicpc.net/problem/1600


방문 처리 배열을 3차원으로 만들어 준다. 나이트처럼 이동하는 것을 점프라고 하면, 


[row][col][이 지점에서 가능한 점프 횟수]


위와 같이 설정해준다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<queue>
 
using namespace std;
int map[201][201], row, col, k;
bool  vis[201][201][31]; //r, c, 점프 가능 횟수
struct Info {
    int r, c, jump, cnt;
};
 
queue<Info> q;
const int dr[4= { 0,0,1,-1 };
const int dc[4= { 1,-1,0,0 };
const int jr[8= { -2,-1,1,2,2,1,-1,-2 };
const int jc[8= { 1,2,2,1,-1,-2,-2,-1 };

void bfs() {
    q.push({ 00, k, 0 });
    vis[0][0][k] = true;
    while (!q.empty()) {
        int qs = q.size();
        while (qs--) {
            
            Info cur = q.front();
            q.pop();
            if (cur.r == row - 1 && cur.c == col - 1) {
                cout << cur.cnt;
                return;
            }
            for (int i = 0; i < 4; i++) {
                int nr = cur.r + dr[i];
                int nc = cur.c + dc[i];
                if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 1continue;
                
                if (vis[nr][nc][cur.jump]) continue//z만큼 점프 개수를 남기고 온적이 있으면 pass
                q.push({ nr, nc, cur.jump, cur.cnt + 1 });
                vis[nr][nc][cur.jump] = true;
                
            }
 
            if (cur.jump <= 0continue;
            for (int i = 0; i < 8 ; i++) {
                int nr = cur.r + jr[i];
                int nc = cur.c + jc[i];
                if (nr < 0 || nc < 0 || nr >= row || nc >= col || map[nr][nc] == 1continue;
                
                if (vis[nr][nc][cur.jump - 1]) continue//z만큼 점프 개수를 남기고 온적이 있으면 pass
                q.push({ nr, nc, cur.jump - 1, cur.cnt + 1 });
                vis[nr][nc][cur.jump - 1= true;
            }
 
        }
    }
    cout << -1;
}
 
int main(void) {
    cin >> k >> col >> row;
    for (int i = 0; i < row; i++
        for (int j = 0; j < col; j++
            cin >> map[i][j];
            
    bfs();
 
    return 0;
}
cs


https://www.acmicpc.net/problem/12851



특정 위치까지 이동할 때 최소 비용을 구해주고, 최소 비용으로 그 위치까지 도달하는 방법의 수를 구해주면 된다.


처음에는 목적지만 중복해서 방문할 수 있도록 해주면 된다고 생각했는데, 이렇게 접근하게 되면


1 -> 2로 가는경우 1+1 로 2로 가는 경우와, 1 * 2로 2로 가는 경우를 모두 잡아낼 수 있지만,


1 -> 4로 가는 경우를 생각해보면 1+1 -> 2, 2 *2 - > 4 로 가는 경우에서 2를 방문 처리한 이후에 재방문을 허용하지 않기 때문에 문제가 된다.


따라서 재방문을 목적지가 아니더라도 허용해주어야 하는데, 당연히 모든 경우에 허용해주면 안되고, 이전에 방문했을 때의 비용과 같은 경우에만 허용해주면 된다.


당연하게도 이전에 방문했던 비용보다 작은 비용으로 재방문하는 경우는 나오지 않는다.



즉, 목적지가 아닌 지점을 재방문 할 때에는, 이미 설정되어 있는 그 지점으로 이동하는 비용과, 현재 지점 + 1 을 비교해서, 같은 경우에는 재방문을 허용한다(큐에 삽입).



목적지인 지점을 재방문 할 경우에는, 위와 같이 비용 비교를 해주고, 동일 비용으로 재방문하는 경우 카운트를 1 증가시켜준다.


목적지를 거쳐서 가는 다른 지점은 방문할 필요가 없기 때문에 큐에 삽입은 하지 않는다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
int m[100001], src, dst, dis[100001];
const int d[3= { 0,1,2 };
queue<int> q;
int cnt = 1//무조건 한 가지 방법은 나온다
void bfs() {
    q.push(src);
    dis[src]++;
    while (!q.empty()) {
        int qs = q.size();
        for (int t = 0; t < qs; t++) {
            int cur = q.front();
            q.pop();
            
            int np;
            for (int i = 0; i < 3; i++) {
                if (d[i] == 0)
                    np = cur + 1;
                else if (d[i] == 1)
                    np = cur - 1;
                else
                    np = cur * 2;
                if (np < 0 || np > 100000continue
                
                //이전에 방문한 적이 있더라도, 동일 비용으로 방문이 가능한 경우
                if (dis[cur] + 1 == dis[np] && dis[np] >= 0){ 
                    if (np == dst) { //목적지인 경우, 그 이후를 탐색할 필요가 없으므로 push 하지 않음
                        cnt++;
                        continue;
                    }
                    else { //이전에 방문한 곳을 여러 방법으로 거쳐갈 수 있으므로 push
                        q.push(np);
                        continue;
                    }
                    
                    //_sleep(500);
                }
 
                //위의 경우를 제외하고 비용이 양수인 경우는, 최소 비용으로 방문하는 경우가 아님
                if (dis[np] >= 0continue
 
                //방문하지 않은 곳을 방문해줌
                dis[np] = dis[cur] + 1;
                q.push(np);
            }
        }
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> src >> dst;
    for (int i = 0; i <= 100000; i++)
        dis[i] = -1;
    bfs();
    
    cout << dis[dst] << '\n' << cnt;
    
    return 0;
}
 
cs


https://www.acmicpc.net/problem/2251



통 A가 비었을때, C에 존재할 수 있는 모든 물의 양의 경우를 출력해주면 된다.


물이 이동할 수 있는 방법은 6가지이다.


a->b, b->c ... 


초기에 각 통의 물의양은 0,0,C 이고, 6가지 모든 경우를 큐에 삽입해주고, a가 0인 순간에만 c의 물의 양을 기록해서 마지막에 출력해주면 된다.


보통 bfs문제를 풀이할 때는 큐에 삽입하는 순간에 방문처리를 해주는데, 이 문제에서는 그렇게 하면 상당히 귀찮아진다.



경우에 따라 bfs의 상단부에서 방문 검사를 해준 직후에 방문처리를 해줄수 있도록 하자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
using namespace std;
struct Info {
    int a, b, c; //a b c 물통의 현재 물의 양
};
queue<Info> q;
bool cVis[201], abVis[201][201]; 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int A, B, C;
    cin >> A >> B >> C; //통의 부피
 
    q.push({ 00, C }); //초기 물은 C에만 가득있음
    //abVis[0][0] = true;
    //cVis[C] = true;
 
    while (!q.empty()) {
        Info cur = q.front(); //현재상태
        q.pop();
        
        //printf("%d %d %d\n", cur.a, cur.b, cur.c);
        
        if (abVis[cur.a][cur.b]) continue;
 
        abVis[cur.a][cur.b] = true;
 
        if (cur.a == 0) {
            cVis[cur.c] = true;
            //printf("%d 추가\n", cur.c);
        }
 
        // a->b
        if (cur.a + cur.b > B) {
            q.push({ cur.a - (B - cur.b), B, cur.c });
            //abVis[cur.a - (B - cur.b)][B] = true;
        }
        else {
            q.push({ 0, cur.a+cur.b, cur.c });
            //abVis[0][cur.a + cur.b] = true;
        }
        // b -> a
        if (cur.b + cur.a > A) {
            q.push({ A, cur.b-(A-cur.a), cur.c });
            //abVis[A][cur.b - (A - cur.a)] = true;
        }
        else {
            q.push({ cur.a + cur.b, 0, cur.c });
            //abVis[cur.a + cur.b][0] = true;
        }
 
        // b->c
        if (cur.b + cur.c > C) {
            q.push({ cur.a, cur.b - (C - cur.c), C });
            //abVis[cur.a][cur.b - (C - cur.c)] = true;
        }
        else {
            q.push({ cur.a, 0, cur.b + cur.c });
        //    abVis[cur.a][0] = true;
        }
 
        //c->b
        if (cur.b + cur.c > B) {
            q.push({cur.a, B, cur.c-(B-cur.b) });
            //abVis[cur.a][B] = true;
        }
        else {
            q.push({ cur.a, cur.b + cur.c, 0 });
            //abVis[cur.a][cur.b + cur.c] = true;
        }
 
        //c->a
        if (cur.c + cur.a > A) {
            q.push({A, cur.b, cur.c-(A-cur.a) });
            //abVis[A][cur.b] = true;
        }
        else {
            q.push({ cur.a + cur.c, cur.b, 0 });
        //    abVis[A][cur.b] = true;
        }
 
        //a->c
        if (cur.c + cur.a > C) {
            q.push({ cur.a-(C-cur.c), cur.b, C });
            //abVis[cur.a - (C - cur.c)][cur.b] = true;
        }
        else {
            q.push({ 0, cur.b, cur.a + cur.c });
            //abVis[0][cur.b] = true;
        }
 
    }
 
    for (int i = 0; i <= C; i++)
        if (cVis[i]) cout << i << ' ';
 
    return 0;
}
 
cs


https://www.acmicpc.net/problem/1525



2차원 배열을 문자열로 맵핑해서 해결한다.



1 2 3

4 5 6

7 8 0 


위와 같은 2차원 배열이라면 "123456780" 이러한 문자열이 되는 것이다.


0의 인덱스로부터 2차원 배열에서 0의 위치를 알아낼 수 있다.



한번의 시행에서, 빈칸의 위치를 옮길 수 있는 위치를 찾아준 다음에, 이전 시행에서 찾은 경우만큼만 bfs를 진행한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
 
const int dzero[4= { -33-11 }; //상하좌우
const int dr[4= { -1,1,0,0 };
const int dc[4= { 0,0,-11 };
 
int main(void) {
    string str ="", dst = "123456780";
    
    for (int i = 0; i < 9; i++) {
        int input;
        cin >> input;
        str += input + '0';
    }
    
    set<string> vis;
    vis.insert(str);
    
    queue<string> q;
    q.push(str);
    int cnt = 0;
    
    while(!q.empty()) {
        int qSize = q.size(); //이전 시행에 찾았던 0이 이동 가능한 경우만 실행
        for (int i = 0; i <qSize; i++) {
            string cur = q.front(); //현재 문자열
            q.pop();
 
            if (cur == dst) { //목적 문자랑 같으면 종료
                cout << cnt;
                return 0;
            }
            //cnt++;
 
            int zeroPos=0//0위치 검색
            for (int j = 0; j < cur.length(); j++) {
                if (cur[j] == '0') {
                    zeroPos = j;
                    break;
                }    
            }
            
            //문자열의 0의 위치로부터 2차원 배열에서의 위치를 맵핑
            int zeroR = zeroPos / 3;
            int zeroC = zeroPos % 3;
 
            for (int j = 0; j < 4; j++) { //0이 움직일 수 있는 방향을 찾음
                int nr = zeroR + dr[j];
                int nc = zeroC + dc[j];
                if (nr < 0 || nc < 0 || nr >= 3 || nc >= 3continue;
                
                string next = cur;
                swap(next[zeroPos], next[zeroPos + dzero[j]]);
 
                if (vis.find(next) == vis.end()){
                    vis.insert(next);
                    q.push(next);
                }
            }
        }
        cnt++//이전에 찾은 경우들 다 해보고 
    }
    cout << -1;
    return 0;
}
 
cs



참고: http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220438835865

https://www.acmicpc.net/problem/9019



문제를 잘못 이해해서 시간을 많이 낭비한 문제이다.


레지스터에 저장될 수 있는 수인 n은, 10000 미만, 0 이상의 수가 맞기는 한데, 무조건 네 자리로 이루어져 있다.


즉 123 이라고 하더라도, 그냥 123이 아니라 _123이라는 것이다. 123에 L연산을 하면 231이 되지만, _123에 L연산을 해봐야


123_ 이고, 결국 123이다.



본인처럼 잘못 이해하고 풀게 되면 시간초과에 걸리게 된다. 틀렸습니다가 아니라 시간 초과라서, 로직이 잘못되었다는 걸 아는데까지 시간이 오래 걸렸다.



마지막에, 최적의 결과를 내기 위한 연산의 흐름을 출력해야 하기 때문에, 큐에 삽입될 때마다 이전 노드와 사용된 연산을 parent 배열에 저장해준다.


parent[다음 수] = {이전 수, 사용된 연산} 이렇게 된다.


마지막에는 결국 parent[목표 수] 부터 시작해서 거꾸로 타고 올라가면서 처음 수가 나올 때까지 사용된 연산을 거꾸로 출력해주면 된다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#pragma warning(disable :4996)
#include<iostream>
#include<queue>
#include<string>
#include<vector>
using namespace std;
 
int T, src, dst;
char cmd[4= { 'D''S''L','R' };
pair<intchar> parent[10000];
 
bool vis[10000];//초기화 필요
queue<int> q;
void bfs() {
    vis[src] = true;
    q.push(src);
 
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        //cout << cur << '\n';
        if (cur == dst) return;
 
        for (int i = 0; i < 4; i++) {
            int next;
            if (cmd[i] == 'D') {
                next = 2 * cur;
                if (next > 9999) next %= 10000;
            }
            else if (cmd[i] == 'S') {
                next = cur - 1;
                if (cur == 0) next = 9999;
            }
            else if (cmd[i] == 'L'
                next = (cur % 1000* 10 + cur / 1000;
            
            else if (cmd[i] == 'R'
                next = (cur % 10* 1000 + cur / 10;
            
            if (vis[next] || next > 10000continue;
            q.push(next);
            vis[next] = true;
            parent[next] = { cur, cmd[i] }; //next로 숫자가 변할 때 사용된 명령
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> T;
    while (T--) {
        cin >> src >> dst;
        bfs();
 
        pair<intchar> prev;
        prev = parent[dst];
        vector<char> v;
        v.push_back(prev.second);
 
        while (1) {
            //cout << prev.first << '\n';
            if (prev.first == src) break;
            prev = parent[prev.first];
            v.push_back(prev.second);
        }
        for (int i = v.size() - 1; i >= 0; i--)
            cout << v[i];
        cout << '\n';
 
        v.clear();
        for (int i = 0; i < 10000; i++)
            vis[i] = false;
        while (!q.empty()) q.pop();
    }
 
    return 0;
}
 
cs


https://www.acmicpc.net/problem/13913



숨바꼭질 시리즈의 네 번째 문제이다. 이 문제는 최단 시간을 구해주고, 동시에 경로를 같이 출력해주면 된다.


경로를 출력하는 방법에는 여러가지가 있을 수 있겠지만, 현재 노드를 다음 노드의 부모라고 보고 parent 배열에 저장해주었다.



다만 이렇게 할 경우, 시작점과 목적지가 같은 경우에 올바른 경로를 출력할 수 없기 때문에 따로 예외 처리를 해주어야 한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int src, dst, m[100002], dr[3= { 0,1,2 }, dis[100002]; //-1, +1, *2
bool vis[100002];
vector<int> path;
queue<int> q;
int parent[100002];
void bfs() {
    
    q.push(src);
    dis[src]++;
    
    path.push_back(src);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (int i = 0; i < 3; i++) {
            int np;
            if (dr[i] == 0) np = cur - 1;
            else if (dr[i] == 1) np = cur + 1;
            else
                np = cur * 2;
 
            if (np < 0 || np > 100000 || dis[np] >= 0continue;
            
            path.push_back(np);
            
            parent[np] = cur; //현재 노드를 다음 노드의 부모로 저장
            q.push(np);
            dis[np] = dis[cur] + 1;
 
        }
    }
}
 
int main(void) {
 
    cin >> src >> dst;
    for (int i = 0; i <= 100000; i++)
        dis[i] = -1;
    bfs();
    cout << dis[dst] << '\n';
    if (src == dst) cout << src; //출발지와 목적지가 같은 경우 예외 처리
    else {
        int prev = parent[dst];
        vector<int> v;
        v.push_back(dst);
        v.push_back(prev);
        while (1) {
            if (prev == src) break//출발지가 나올 때까지 타고 올라감
            prev = parent[prev];
            v.push_back(prev);
        }
        for (int i = v.size() - 1; i >= 0; i--)
            cout << v[i] << ' ';
    }
 
    return 0;
}
cs


https://www.acmicpc.net/problem/14503



로봇의 위치와 방향을 관리하며 bfs를 돌려주면 된다. 모든 순간에 로봇은 하나이기 때문에 큐에는 최대 하나의 좌표(로봇의 좌표)만 들어갈 수 있다.




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<iostream>
#include<queue>
using namespace std;
typedef pair<intint> pii;
struct Robot {
    int r, c;
}bot;
int dir;
int row, col, m[51][51];
bool vis[51][51];
queue<Robot> q;
int dr[4= { -1010 };
int dc[4= { 010-1 };
int cnt = 1;
pii getBackPos(int r, int c, int dir) {
    if (dir == 0)
        return { r + 1, c };
    else if (dir == 1)
        return { r, c - 1 };
    else if (dir == 2)
        return { r - 1, c };
    else
        return { r, c + 1 };
}
void bfs(Robot bot) {
    q.push(bot);
    vis[bot.r][bot.c] = true// 로봇 시작 위치 청소
    while (!q.empty()) {
        Robot cur = q.front();
        q.pop();
        //int doneCnt = 0;
        bool goBack = true;
        for (int i = 0; i < 4; i++) {
            dir = (dir + 3) % 4;
            int nr = cur.r + dr[dir];
            int nc = cur.c + dc[dir];
            if (nr < 0 || nc < 0 || nr >= row || nc >= col || vis[nr][nc] !=0 || m[nr][nc] != 0) {
                //doneCnt++;
                continue;
            }
 
            else {
                //printf("%d, %d 방향 %d에서 %d, %d 방향 %d로 이동\n", cur.r, cur.c, cur.dir, nr, nc, (cur.dir+3)%4);
                q.push({ nr, nc });
                vis[nr][nc] = true;
                cnt++;
                goBack = false;
                break;
            }
        }
        //if (doneCnt == 4) {
        if(goBack){
            //dir = (dir + 1) % 4;
            //printf("%d %d 방향 %d 상태에서 후진시도\n", cur.r, cur.c, cur.dir);
            pii tmp = getBackPos(cur.r, cur.c, dir);
            if (tmp.first < 0 || tmp.second < 0 || tmp.first >= row || tmp.second >= col
                 || m[tmp.first][tmp.second] == 1)
                return;
 
            //후진 가능한경우
            else {
                q.push({ tmp.first, tmp.second});
                
            }
    
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> row >> col;
    cin >> bot.r >> bot.c >> dir;
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            cin >> m[i][j];
    
    bfs(bot);
    
    cout << cnt;
    return 0;
}
 
cs


+ Recent posts