BOJ#2931 가스관
* 문제
* 풀이
이 문제는 어려운 문제인지, 쉬운 문제인지 헷갈리네요.
- 삭제된 노드는 단 1개이고 쉽게 찾을 수 있다. (출발점에서 파이프를 따라가보면 삭제된 노드가 나온다)
- 위치는 구했고 거기에 맞는 파이프만 찾으면 되는데
노드에서 출입구가 몇개이고 어느 방향으로 뚫려있는지만 알면? 파이프를 구할 수 있다.
쉽다고 생각하면 쉬운데,,,
정형화된(?) bfs, dfs 탐색으로는 어떻게 풀까? 문제 의도는 뭘까
아무튼 bfs, dfs 몰라도 자기 생각을 코드로 옮길 수 있으면 이 문제는 쉽게 풀 수 있을 것 같습니다.
입사 시험에 적당한 문제
↓ 테스트 케이스 보기 (클릭) ↓
* 나의 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* BOJ#2931 가스관
* https://www.acmicpc.net/problem/2931
*/
public class Main {
static final int BLANK = 10;
static final int START = 11;
static final int END = 12;
static final int BLOCK_1 = 1;
static final int BLOCK_2 = 2;
static final int BLOCK_3 = 3;
static final int BLOCK_4 = 4;
static final int BLOCK_C = 5;
static final int BLOCK_V = 6;
static final int BLOCK_H = 7;
static final int WEST = 0;
static final int NORTH = 1;
static final int EAST = 2;
static final int SOUTH = 3;
static final int FALSE = 5;
static final int[] dRow = {0, -1, 0, 1};
static final int[] dCol = {-1, 0, 1, 0};
static final char[] pipeArr = {'.', '1', '2', '3', '4', '+', '|', '-'};
static int R, C;
static int[][] map = new int[26][26];
public static void main(String[] args) throws IOException {
int sRow = 0, sCol = 0;
int eRow = 0, eCol = 0;
// input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
for (int i = 0; i < R; i++) {
String s = br.readLine();
for (int j = 0; j < C; j++) {
char c = s.charAt(j);
switch (c) {
case '.':
map[i][j] = BLANK;
break;
case 'M':
map[i][j] = START;
sRow = i;
sCol = j;
break;
case 'Z':
map[i][j] = END;
eRow = i;
eCol = j;
break;
case '|':
map[i][j] = BLOCK_V;
break;
case '-':
map[i][j] = BLOCK_H;
break;
case '+':
map[i][j] = BLOCK_C;
break;
default:
map[i][j] = c - '0';
break;
}
}
}
// solve
// M에서부터 삭제된 노드까지 추적한다. return 삭제된 노드, 출입구 정보
Node M = null;
for (int dir = 0; dir < 4; dir++) {
int nextRow = sRow + dRow[dir];
int nextCol = sCol + dCol[dir];
if (nextRow < 0 || nextRow >= R || nextCol < 0 || nextCol >= C) continue;
// 출발점 노드와 인접한 노드들 중 유효한 노드(파이프)를 찾는다.
if (getStartNode(nextRow, nextCol, dir)) {
M = traceRoute(nextRow, nextCol, dir);
}
}
// Z에서부터 삭제된 노드까지 추적한다. return 삭제된 노드, 출입구 정보
Node Z = null;
for (int dir = 0; dir < 4; dir++) {
int nextRow = eRow + dRow[dir];
int nextCol = eCol + dCol[dir];
if (nextRow < 0 || nextRow >= R || nextCol < 0 || nextCol >= C) continue;
// 출발점 노드와 인접한 노드들 중 유효한 노드(파이프)를 찾는다.
if (getStartNode(nextRow, nextCol, dir)) {
Z = traceRoute(nextRow, nextCol, dir);
}
}
// 찾아낸 삭제된 노드 주변에 유효햔 파이프가 몇개인지 확인, 3개 이상인 경우 + 파이프가 들어가야 한다
int cnt = 0;
for (int dir = 0; dir < 4; dir++) {
int nextRow = M.row + dRow[dir];
int nextCol = M.col + dCol[dir];
if (nextRow < 0 || nextRow >= R || nextCol < 0 || nextCol >= C) continue;
if (getStartNode(nextRow, nextCol, dir)) {
cnt++;
}
}
// 결과 출력
if (cnt >= 3) {
// + 파이프인 경우
System.out.println((M.row + 1) + " " + (M.col + 1) + " " + pipeArr[BLOCK_C]);
} else {
// + 파이프가 아닌 경우, 출입구 정보 2개를 이용하여 파이프를 찾는다
System.out.println((M.row + 1) + " " + (M.col + 1) + " " + getBlock(M.entrance | Z.entrance));
}
} // ~main
// + 파이프가 아닌 경우, 출입구 정보 2개를 이용하여 파이프를 찾는다
static char getBlock(int enterance) {
if ((enterance & (1 << NORTH)) > 0
&& (enterance & (1 << SOUTH)) > 0) {
return pipeArr[BLOCK_V];
}
if ((enterance & (1 << WEST)) > 0
&& (enterance & (1 << EAST)) > 0) {
return pipeArr[BLOCK_H];
}
if ((enterance & (1 << EAST)) > 0
&& (enterance & (1 << SOUTH)) > 0) {
return pipeArr[BLOCK_1];
}
if ((enterance & (1 << NORTH)) > 0
&& (enterance & (1 << EAST)) > 0) {
return pipeArr[BLOCK_2];
}
if ((enterance & (1 << WEST)) > 0
&& (enterance & (1 << NORTH)) > 0) {
return pipeArr[BLOCK_3];
} else {
return pipeArr[BLOCK_4];
}
}
// (row, col) 노드가 유효한지(출발점과 연결된 파이프인지) 판단한다.
static boolean getStartNode(int row, int col, int inlet) {
if (map[row][col] >= BLOCK_1 && map[row][col] <= BLOCK_H) {
inlet = (inlet + 2) % 4;
if (getOutlet(map[row][col], inlet) != FALSE) return true;
}
return false;
}
// 경로 추적
static Node traceRoute(int row, int col, int inlet) {
if (map[row][col] >= BLOCK_1 && map[row][col] <= BLOCK_H) {
inlet = (inlet + 2) % 4;
int outlet = getOutlet(map[row][col], inlet);
int nextRow = row + dRow[outlet];
int nextCol = col + dCol[outlet];
return traceRoute(nextRow, nextCol, outlet);
} else if (map[row][col] == BLANK) {
return new Node(row, col, 1 << ((inlet + 2) % 4));
}
return null;
}
// 파이프와 입구 위치를 입력받고, 출구 위치를 반환한다
static int getOutlet(int pipe, int inlet) {
int outlet = 0;
switch (pipe) {
case BLOCK_1:
outlet = inlet == SOUTH ? EAST : inlet == EAST ? SOUTH : FALSE;
break;
case BLOCK_2:
outlet = inlet == NORTH ? EAST : inlet == EAST ? NORTH : FALSE;
break;
case BLOCK_3:
outlet = inlet == WEST ? NORTH : inlet == NORTH ? WEST : FALSE;
break;
case BLOCK_4:
outlet = inlet == WEST ? SOUTH : inlet == SOUTH ? WEST : FALSE;
break;
case BLOCK_C:
outlet = inlet == WEST ? EAST : inlet == NORTH ? SOUTH : inlet == EAST ? WEST : NORTH;
break;
case BLOCK_V:
outlet = inlet == NORTH ? SOUTH : inlet == SOUTH ? NORTH : FALSE;
break;
case BLOCK_H:
outlet = inlet == WEST ? EAST : inlet == EAST ? WEST : FALSE;
break;
}
return outlet;
}
}
class Node {
int row, col;
int entrance;
Node(int row, int col, int entrance) {
this.row = row;
this.col = col;
this.entrance = entrance;
}
}
'Algorithm > 시뮬레이션' 카테고리의 다른 글
| BOJ#11559 Puyo Puyo (0) | 2017.09.21 |
|---|---|
| BOJ#14503 로봇 청소기 (0) | 2017.04.22 |
| BOJ#3190 뱀 (5) | 2017.04.15 |
| BOJ#10875 뱀 (0) | 2017.04.14 |
| BOJ#14499 주사위 굴리기 (1) | 2017.04.11 |