반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. BFS


버스가 가로인 상태에서는 가로, 대각선이 되고

대각선인 상태에서는 가로, 대각선, 세로가 되고

세로인 상태에서는 세로, 대각선이 된다.


이때 dy와 dx의 값을 가로, 대각선, 세로 방향으로 인덱스를 두게되면


가로인 상태에서는 0,1을 쓰고 대각선일때는 0,1,2를 쓰고 세로일 때는 1,2를 쓰면 된다.


그 외에는 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
#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
 
// 가로 0 대각선 1 세로 2
int dy[3= { 0,1,};
int dx[3= { 1,1,};
 
int arr[35][35];
 
struct INFO {
    int y, x, dir;
};
 
int main() {
    int n;
    scanf("%d"&n);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d"&arr[i][j]);
 
    int ans = 0;
    queue<INFO> q;
 
    q.push({ 0,1,});
 
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int dir = q.front().dir;
        q.pop();
 
        if (y == n - && x == n - 1)
            ans++;
 
        if (dir == 0) {
            for (int i = 0; i < 2; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                int nDir = i;
                if (<= ny && ny < n && <= nx && nx < n && !arr[ny][nx]) {
                    if (nDir == && !arr[ny - 1][nx] && !arr[ny][nx - 1])
                        q.push({ ny,nx, nDir });
                    else if(nDir != 1)
                        q.push({ ny,nx, nDir });
                }
 
            }
        }
        else if (dir == 1) {
            for (int i = 0; i < 3; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                int nDir = i;
                if (<= ny && ny < n && <= nx && nx < n && !arr[ny][nx]) {
                    if (nDir == && !arr[ny - 1][nx] && !arr[ny][nx - 1])
                        q.push({ ny,nx, nDir });
                    else if (nDir != 1)
                        q.push({ ny,nx, nDir });
                }
            }
        }
        if (dir == 2) {
            for (int i = 1; i < 3; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                int nDir = i;
                if (<= ny && ny < n && <= nx && nx < n && !arr[ny][nx]) {
                    if (nDir == && !arr[ny - 1][nx] && !arr[ny][nx - 1])
                        q.push({ ny,nx, nDir });
                    else if (nDir != 1)
                        q.push({ ny,nx, nDir });
                }
            }
        }
    }
    printf("%d\n", ans);
 
    return 0;
}
cs

반응형