728x90
반응형
https://www.acmicpc.net/problem/2931
2931번: 가스관
문제 러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다. 이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다. 가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직,
www.acmicpc.net
|
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
#include<stdio.h>
#include<iostream>
#define NSIZE 26
#define MSIZE 26
using namespace std;
int N, M;
int sy, sx, ey, ex;
char input[NSIZE][MSIZE];
int chk[NSIZE][MSIZE];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
bool up(int r, int c) {
int R = N; int C = M;
return r > 0 && (input[r - 1][c] == '|' || input[r - 1][c] == '+' || input[r - 1][c] == '1' || input[r - 1][c] == '4');
}
bool down(int r, int c) {
int R = N; int C = M;
return r < R - 1 && (input[r + 1][c] == '|' || input[r + 1][c] == '+' || input[r + 1][c] == '2' || input[r + 1][c] == '3');
}
bool left(int r, int c) {
int R = N; int C = M;
return c > 0 && (input[r][c - 1] == '-' || input[r][c - 1] == '1' || input[r][c - 1] == '+' || input[r][c - 1] == '2');
}
bool right(int r, int c) {
int R = N; int C = M;
return c < C - 1 && (input[r][c + 1] == '-' || input[r][c + 1] == '+' || input[r][c + 1] == '3' || input[r][c + 1] == '4');
}
void init() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
scanf(" %s", input[i]);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (input[i][j] == 'M') {
sy = i; sx = j;
ey = i; ex = j;
}
}
}
}
void dfs(int y, int x) {
for (int dir = 0; dir < 4; dir++) {
int ny = y + dy[dir]; int nx = x + dx[dir];
if (input[ny][nx] != '.') {
if ((dir==0||dir==1)&&input[ny][nx] == '|'&&chk[ny][nx]==0) {
chk[ny][nx] = 1;
dfs(ny, nx);
chk[ny][nx] = 0;
}
else if ((dir == 2 || dir == 3) && input[ny][nx] == '-' && chk[ny][nx] == 0) {
chk[ny][nx] = 1;
dfs(ny, nx);
chk[ny][nx] = 0;
}
else if (input[ny][nx] == '+' && chk[ny][nx] == 0) {
chk[ny][nx] = 1;
dfs(ny, nx);
chk[ny][nx] = 0;
}
else if ((dir == 0 || dir == 2) && input[ny][nx] == '1' && chk[ny][nx] == 0) {
chk[ny][nx] = 1;
dfs(ny, nx);
chk[ny][nx] = 0;
}
else if ((dir == 1 || dir == 2) && input[ny][nx] == '2' && chk[ny][nx] == 0) {
chk[ny][nx] = 1;
dfs(ny, nx);
chk[ny][nx] = 0;
}
else if ((dir == 3 || dir == 1) && input[ny][nx] == '3' && chk[ny][nx] == 0) {
chk[ny][nx] = 1;
dfs(ny, nx);
chk[ny][nx] = 0;
}
else if ((dir == 3|| dir == 0) && input[ny][nx] == '4' && chk[ny][nx] == 0) {
chk[ny][nx] = 1;
dfs(ny, nx);
chk[ny][nx] = 0;
}
}
}
if (input[y][x] == '|') {
if (input[y - 1][x] == '.') { sy = y-1; sx = x; return; }
if(input[y+1][x]=='.') { sy = y+1; sx = x; return; }
}
if (input[y][x] == '-') {
if (input[y][x-1] == '.') { sy = y; sx = x-1; return; }
if (input[y][x+1] == '.') { sy = y; sx = x+1; return; }
}
if (input[y][x] == '+') {
if (input[y - 1][x] == '.') { sy = y-1; sx = x; return; }
if (input[y + 1][x] == '.') { sy = y+1; sx = x; return; }
if (input[y][x - 1] == '.') { sy = y; sx = x-1; return; }
if (input[y][x + 1] == '.') { sy = y; sx = x+1; return; }
}
if (input[y][x] == '1') {
if (input[y + 1][x] == '.') { sy = y+1; sx = x; return; }
if (input[y][x + 1] == '.') { sy = y; sx = x+1; return; }
}
if (input[y][x] == '2') {
if (input[y - 1][x] == '.') { sy = y-1; sx = x; return; }
if (input[y][x + 1] == '.') { sy = y; sx = x+1; return; }
}
if (input[y][x] == '3') {
if (input[y - 1][x] == '.') { sy = y-1; sx = x; return; }
if (input[y][x - 1] == '.') { sy = y; sx = x-1; return; }
}
if (input[y][x] == '4') {
if (input[y][x - 1] == '.') { sy = y; sx = x-1; return; }
if (input[y + 1][x] == '.') { sy = y+1; sx = x; return; }
}
}
int main(void) {
init();
dfs(sy, sx);
if (up(sy, sx) && down(sy, sx)) {
if (!(input[sy][sx - 1] == '-' || input[sy][sx - 1] == '+' || input[sy][sx - 1] == '1' || input[sy][sx - 1] == '2' || input[sy][sx + 1] == '-' || input[sy][sx + 1] == '+' || input[sy][sx + 1] == '3' || input[sy][sx + 1] == '4')) {
printf("%d %d |\n", sy + 1, sx + 1);
}
}
if (right(sy, sx) && left(sy, sx)) {
if (!(input[sy - 1][sx] == '|' || input[sy - 1][sx] == '+' || input[sy - 1][sx] == '1' || input[sy - 1][sx] == '4' || input[sy + 1][sx] == '|' || input[sy + 1][sx] == '+' || input[sy + 1][sx] == '2' || input[sy + 1][sx] == '3')) {
printf("%d %d -\n", sy + 1, sx + 1);
}
}
if (up(sy, sx) && down(sy, sx) && right(sy, sx) && left(sy, sx)) {
printf("%d %d +\n", sy + 1, sx + 1);
}
if (right(sy, sx) && down(sy, sx)) {
if (!(input[sy - 1][sx] == '|' || input[sy - 1][sx] == '+' || input[sy - 1][sx] == '1' || input[sy - 1][sx] == '4'|| input[sy][sx - 1] == '-' || input[sy][sx - 1] == '+' || input[sy][sx - 1] == '1' || input[sy][sx - 1] == '2')) {
printf("%d %d 1\n", sy + 1, sx + 1);
}
}
if (up(sy, sx) && right(sy, sx)) {
if (!(input[sy + 1][sx] == '|' || input[sy + 1][sx] == '+' || input[sy + 1][sx] == '2' || input[sy + 1][sx] == '3' || input[sy][sx - 1] == '-' || input[sy][sx - 1] == '+' || input[sy][sx - 1] == '1' || input[sy][sx - 1] == '2')) {
printf("%d %d 2\n", sy + 1, sx + 1);
}
}
if (up(sy, sx) && left(sy, sx)) {
if (!(input[sy + 1][sx] == '|' || input[sy + 1][sx] == '+' || input[sy + 1][sx] == '2' || input[sy + 1][sx] == '3' || input[sy][sx + 1] == '-' || input[sy][sx + 1] == '+' || input[sy][sx + 1] == '3' || input[sy][sx + 1] == '4')) {
printf("%d %d 3\n", sy + 1, sx + 1);
}
}
if (down(sy, sx) && left(sy, sx)) {
if (!(input[sy - 1][sx] == '|' || input[sy - 1][sx] == '+' || input[sy - 1][sx] == '1' || input[sy - 1][sx] == '4' || input[sy][sx + 1] == '-' || input[sy][sx + 1] == '+' || input[sy][sx + 1] == '3' || input[sy][sx + 1] == '4')) {
printf("%d %d 4\n", sy + 1, sx + 1);
}
}
return 0;
}
|
이문제는 엄청 어렵지는 않지만 좀 까다로운 문제같습니다. 소스를 짜다 보니 길어졌는데 포인트는
가스관이 뚫려 있는 위치를 찾는것입니다. D로 부터 dfs를 돌려서 비어있는 공간을 찾고
그 공간에 대해서 확인을 하느식으로 구현을 했습니다.
정말 멍청한 방법으로 푼것이 아닐까 생각은되지만 우선적으로 비어있는 공간을 찾는것은 어찌보면 효율적이라고
생각이 듭니다. 그리고 나서 가장 포인트가되는것은 그위치에 맞는 블록인지 확인하는 절차였습니다.
그냥 한다면 예외 경우가 생기기때문에 이런 포인트를 잘 봐야합니다.
그냥 넣으면 분명 이러실것입니다. 예제는 맞는데 도대체 틀린 부분이 어딘지 모르겠다는
그렇습니다. 저부분이 대게 틀렸을껍니다. 저위치는 + 가 들어가야하는데 위아래로 연결가능한
파이프가 먼저들어가면 틀린답이기 떄문입니다.
그러기위해서는 정말 자신의 위치가 맞는지에 대해서 한번더 조건을 확인해서 걸러주면
답이 맞을꺼라 생각합니다. 소스를 풀어서 설명 드리고싶은데 엄두가 안나네요.
질문에 대해서만 답변 드리겠습니다.
오늘은 여기까지 입니다. 감사합니다.
728x90
반응형
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 13549 숨바꼭질3 (0) | 2019.10.03 |
|---|---|
| 백준 2065 나룻배 (0) | 2019.10.02 |
| 백준 16137 견우와 직녀 (0) | 2019.09.30 |
| 백준 4577 소코반 (0) | 2019.09.30 |
| 백준 1260 DFS와 BFS (0) | 2019.09.29 |
댓글