문제 URL : www.acmicpc.net/problem/2931
2931번: 가스관
러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다.
www.acmicpc.net
문제접근법 : 전수조사를 통해 해결했습니다.
어떻게 전수 조사를 했냐면 board[i][j]== '.' 일경우 "|-1234+"를 넣어서 조사합니다.
그러나 여기서 순서가 중요한데 +를 제외한 나머지는 순서는 상관없지만 +를 넣는경우는 항상 나중에 합니다.
왜냐하면 | 를 넣어서 해결할수있는걸 +를 넣어서도 해결할수있기때문에 순서가 중요합니다.
또한 파이프가 +모양인곳은 반드시 2번 거처가기때문에 몇번을 거첬는지 확인하는것도 중요합니다.
또한 도착지점의 파이프를 + 로 생각해야 어떤 지점이든 바로 들어올수가있습니다. 그러나 도착지점은 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
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
|
//By 콩순이냉장고
#include <string>
#include<cstdio>
#include <unordered_set>
#include <iostream>
#include <vector>
using namespace std;
int idx[255];
int n, m;
char board[30][30];
int sy, sx;
string p = "|-1234+"; //+는 늘 나중에탐색하기위해
int cnt;
int pipe[7][4] = { //파이프 모양
{1,0,1,0},
{0,1,0,1},
{0,1,1,0},
{1,1,0,0},
{1,0,0,1},
{0,0,1,1},
{1,1,1,1}
};
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int dir[7][4] = { //파이프마다 들어올때 나가는방향을 저장해줌
{2,-1,0,-1},
{-1,3,-1,1},
{-1,2,1,-1},
{1,0,-1,-1},
{3,-1,-1,0},
{-1,-1,3,2},
{2,3,0,1}
};
bool isrange(int y, int x) {
return 1 <= y && y <= n && 1 <= x && x <= m;
}
void input() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
if (board[i][j] == 'M') {
sy = i;
sx = j;
}
if (board[i][j] != '.') {
if (board[i][j] == '+')//밟아야할땅이 2번
cnt += 2;
else//그외는 한번
cnt++;
}
}
}
}
void init() {
for (int i = 0; i < p.size(); i++)
idx[p[i]] = i;
idx['Z'] = 6;
idx['M'] = 6;
}
void backtrack(int y, int x,int d,bool &flag,int walk=1) {
if (board[y][x] == 'Z') {
if(walk==cnt)//밟은땅이 cnt라면 도착
flag = true;
return;
}
int ny = y + dy[d];
int nx = x + dx[d];
int ntunnel = idx[board[ny][nx]];
if (isrange(ny, nx) && board[ny][nx] != '.') {
if (pipe[ntunnel][(d+2)%4]&&dir[ntunnel][(d+2)%4]>=0) {//다음 파이프터널을 통해 들어갈수있고 방향이 올바르다면
backtrack(ny, nx, dir[ntunnel][(d + 2) % 4], flag,walk+1);//다음 방향 dir[ntunnel][(d+2)%4] 이게 가장중요
}
}
}
void solve() {
bool flag = false;
init();
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) {
if (board[i][j] == '.') {
for (int k = 0; k < 7; k++) {
board[i][j] = p[k];
if (k == 6)//+파이프라면 2번밟아야함
cnt += 2;
else //그외는 한번
cnt++;
for (int d = 0; d < 4; d++) {
backtrack(sy, sx,d, flag);
if (flag) {
cout << i << " " << j << " " << board[i][j] << "\n";
return;
}
}
//원상복구
if (k == 6)
cnt -= 2;
else
cnt--;
}
board[i][j] = '.';
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
논리적인 오류 혹은 더좋은 아이디어
궁금한점 혹은 모르는점 이있다면 언제든지 댓글을 이용해주시면 감사합니당
'백준' 카테고리의 다른 글
| 백준 17130 토끼가 정보섬에 올라온 이유 (0) | 2021.04.16 |
|---|---|
| 백준 1600 말이 되고픈 원숭이 (0) | 2021.04.05 |
| 백준 14888 연산자 끼워넣기 (0) | 2021.02.17 |
| 백준 14502 연구소 (0) | 2021.02.17 |
| 백준 2568 전깃줄 - 2 (0) | 2021.02.15 |