반응형
문제
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
풀이
bfs와 dp를 섞은 듯한 재밌는 문제였습니다.
q는 순서대로 현재 파이프 끝의 x좌표 / y좌표 / 상태를 저장합니다.
q에다가 push와 pop을 반복하면서, 갈 수 있는 경로의 수를 파악합니다.
각각의 상태에 대해 취할 수 있는 다음 상태를 하드 코딩 했는데, 따로 함수를 만들었다면 더욱 깔끔한 코드가 되었을 것 같습니다.
소스 코드
|
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#include<iostream>
#include<algorithm>
#include <queue>
using namespace std;
int map[16][16];
int dp[16][16];
int N;
// q : x, y, 파이프 상태
// 파이프 상태 (0 : 가로, 1 : 대각선, 2 : 세로)
void bfs()
{
dp[0][1] = 1;
queue<pair<pair<int, int>, int>> q;
q.push(make_pair(make_pair(1, 0), 0));
while (!q.empty())
{
int x = q.front().first.first;
int y = q.front().first.second;
int state = q.front().second;
int nx, ny = 0;
q.pop();
//가로 일 때
if (state == 0)
{
//가로
nx = x + 1;
ny = y;
if (nx < N)
{
if (map[ny][nx] == 0)
{
dp[ny][nx]++;
q.push(make_pair(make_pair(nx, ny), 0));
}
}
//대각선
nx = x + 1;
ny = y + 1;
if (nx < N && ny < N)
{
if (map[ny][x] == 0 && map[y][nx] == 0 && map[ny][nx] == 0)
{
dp[ny][nx]++;
q.push(make_pair(make_pair(nx, ny), 1));
}
}
}
//대각선 일 때
else if (state == 1)
{
//가로
nx = x + 1;
ny = y;
if (nx < N)
{
if (map[ny][nx] == 0)
{
dp[ny][nx]++;
q.push(make_pair(make_pair(nx, ny), 0));
}
}
//대각선
nx = x + 1;
ny = y + 1;
if (nx < N && ny < N)
{
if (map[ny][x] == 0 && map[y][nx] == 0 && map[ny][nx] == 0)
{
dp[ny][nx]++;
q.push(make_pair(make_pair(nx, ny), 1));
}
}
//세로
nx = x;
ny = y + 1;
if (ny < N)
{
if (map[ny][nx] == 0)
{
dp[ny][nx]++;
q.push(make_pair(make_pair(nx, ny), 2));
}
}
}
//세로 일 때
else
{
//대각선
nx = x + 1;
ny = y + 1;
if (nx < N && ny < N)
{
if (map[ny][x] == 0 && map[y][nx] == 0 && map[ny][nx] == 0)
{
dp[ny][nx]++;
q.push(make_pair(make_pair(nx, ny), 1));
}
}
//세로
nx = x;
ny = y + 1;
if (ny < N)
{
if (map[ny][nx] == 0)
{
dp[ny][nx]++;
q.push(make_pair(make_pair(nx, ny), 2));
}
}
}
}
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> map[i][j];
}
}
bfs();
cout << dp[N - 1][N - 1];
return 0;
}
|
cs |
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준 1068] 트리 (C++) (0) | 2021.08.25 |
|---|---|
| [백준 3020] 개똥벌레 (C++) (0) | 2021.08.24 |
| [백준 14500] 테트로미노 (C++) (0) | 2021.08.21 |
| [백준 11507] 오르막 수 (C++) (0) | 2021.08.21 |
| [백준 17609] 회문 C++ (0) | 2021.08.21 |