algorithm codes/baekjoon online judge
17070번: 파이프 옮기기 1 (백준 온라인 저지, C++)
mimizzang
2019. 5. 1. 18:03
문제 풀이
파이프를 옮기면서 목적지까지 도달할 수 있는 경우의 수를 고르는 문제입니다. 파이프의 좌표에 유의하여 문제를 풀이하였습니다. 우선 파이프의 초기 좌표는 pipe1 = (1,1), pipe2 = (1,2)입니다.
이 때 파이프를 옮기게 되면, pipe1은 항상 pipe2의 위치로 이동하게 됩니다.
pipe2의 경우, 각각 가로로 있는 경우와 세로로 있는 경우, 대각선으로 있는 경우를 고려하여 좌표를 이동시켜 주면 됩니다. 벽이 있는 경우와 지도를 탈출하는 경우에 주의합니다. 이 후 pipe2가 목적지에 도착하였다면, 결과값에 추가시켜 줍니다.
코드
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
|
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int n, ans;
int arr[17][17];
int dx[] = {0, 1, 1};
int dy[] = {1, 1, 0};
void movePipe(pair<int,int> p1, pair<int,int> p2) {
if (p2 == make_pair(n, n)) {
ans++;
}
pair<int, int> tmp_p2;
for (int i = 0; i < 3; i++) {
tmp_p2 = p2;
if (tmp_p2.first <= n && tmp_p2.second <= n && tmp_p2.first > 0 && tmp_p2.second > 0 && arr[tmp_p2.first][tmp_p2.second] == 0) {
if (i == 1) {
if ((x1 <= n && x1 > 0 && y1 <= n && y1 > 0) && (arr[x1][y1] == 1)) continue;
if ((x2 <= n && x2 > 0 && y2 <= n && y2 > 0) && (arr[x2][y2] == 1)) continue;
movePipe(p2, tmp_p2);
}
else {
movePipe(p2, tmp_p2);
}
}
}
}
int main() {
ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> arr[i][j];
}
}
pair<int, int> init_p1 = { 1,1 }, init_p2 = { 1,2 };
movePipe(init_p1, init_p2);
cout << ans << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter
|
제출 결과
문제 출처
https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이
www.acmicpc.net