문제
이해
M -> Z 까지 향하는 가스관이 있습니다. 가스는 각 블록의 모양대로 진행합니다.
입력으로는 가스관을 하나 제거한 상태로 주어집니다.
제거된 가스관의 위치와 원래의 모양을 출력하면 됩니다.
단, 입력으로 주어지는 보드에서 M, Z가 하나의 블록과 이어져 있는 경우만 주어집니다. (M, Z 인접한 블록이 제거되는 경우는 없습니다.)
그리고 불필요한 블록이 존재하지 않습니다.
접근
조건이 친절한 문제인 것 같습니다. 격자의 크기는 25x25이고 불필요한 블록이 없기 때문에 항상 가스는 한 가지의 경로로만 움직여 도착지에 도달합니다. 단순 시뮬레이션 문제로 보여집니다.
출발지와 도착지가 주어지고 없어진 가스관을 찾으면 됩니다. 작성해야 할 로직에 대해서 생각해보면 다음과 같습니다.
- 출발지부터 가스 출발 (항상 한 방향으로만 정해져있음)
- 없어진 블록이 있다면 해당 위치에서 어떤 블록이 알맞은지 탐색
- 출력
간단해보이지만 사실 가스관의 생김새 때문에 정말 많은 분기문을 작성해야 합니다. 가스가 흐르는 방향에 따라 가스관의 모양이 달라지기 때문입니다.
단순 분기문으로 어느 가스관이 알맞은지를 확인해도 되지만 단순하게 모든 블록 모양을 넣어보고 가능한 경우를 출력하도록 코드를 작성했습니다.
풀이
private static boolean CheckBoard() {
Point cur = new Point(start.x, start.y);
int dir = initDir;
while (true) {
int nx = cur.x + d[0][dir];
int ny = cur.y + d[1][dir];
if (IsOutBound(nx, ny)) {
return false;
}
if (board[nx][ny] == '.') {
ans = new Point(nx, ny);
ansPipe = CheckPipe(nx, ny);
return false;
} else if (board[nx][ny] == 'Z') {
return true;
} else {
cur.x = nx;
cur.y = ny;
int newDir = GetDirByPipe(nx, ny, dir);
if (newDir == -1) {
return false;
} else {
dir = newDir;
}
}
}
}위는 제거된 블록의 모양을 확인하는 코드입니다. 출발지부터 시작하여 가스의 흐름따라 한 칸씩 확인합니다. 격자의 모양이 '.'이라면 제거된 블록의 위치이므로 해당 위치에서 어떤 모양인지 판단합니다. 판단의 세부 로직은 모든 블록모양을 넣어보고 가스의 흐름이 정상적인지 확인합니다.
전체 코드
결과
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.awt.Point;
public class prob2931_2 {
static final int[][] d = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };
static char[][] board;
static int N, M;
static StringTokenizer st = null;
static Point start;
static Point ans;
static char ansPipe;
static int initDir;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new char[N + 1][M + 1];
for (int i = 1; i <= N; i++) {
String s = br.readLine();
for (int j = 1; j <= M; j++) {
board[i][j] = s.charAt(j - 1);
if (board[i][j] == 'M') {
start = new Point(i, j);
}
}
}
initDir = -1;
for (int i = 0; i < 4; i++) {
int nx = start.x + d[0][i];
int ny = start.y + d[1][i];
if (IsOutBound(nx, ny)) {
continue;
}
if (board[nx][ny] != '.') {
initDir = i;
}
}
CheckBoard();
System.out.println(ans.x + " " + ans.y + " " + ansPipe);
}
private static boolean CheckBoard() {
Point cur = new Point(start.x, start.y);
int dir = initDir;
while (true) {
int nx = cur.x + d[0][dir];
int ny = cur.y + d[1][dir];
if (IsOutBound(nx, ny)) {
return false;
}
if (board[nx][ny] == '.') {
ans = new Point(nx, ny);
ansPipe = CheckPipe(nx, ny);
return false;
} else if (board[nx][ny] == 'Z') {
return true;
} else {
cur.x = nx;
cur.y = ny;
int newDir = GetDirByPipe(nx, ny, dir);
if (newDir == -1) {
return false;
} else {
dir = newDir;
}
}
}
}
private static boolean CheckBoard2() {
Point cur = new Point(start.x, start.y);
int dir = initDir;
while (true) {
int nx = cur.x + d[0][dir];
int ny = cur.y + d[1][dir];
if (IsOutBound(nx, ny)) {
return false;
}
if (board[nx][ny] == 'Z') {
return true;
} else {
cur.x = nx;
cur.y = ny;
int newDir = GetDirByPipe(nx, ny, dir);
if (newDir == -1) {
return false;
} else {
dir = newDir;
}
}
}
}
private static char CheckPipe(int x, int y) {
board[x][y] = '|';
if (CheckBoard2())
return '|';
board[x][y] = '-';
if (CheckBoard2())
return '-';
board[x][y] = '+';
if (CheckBoard2())
return '+';
board[x][y] = '1';
if (CheckBoard2())
return '1';
board[x][y] = '2';
if (CheckBoard2())
return '2';
board[x][y] = '3';
if (CheckBoard2())
return '3';
board[x][y] = '4';
if (CheckBoard2())
return '4';
return '.';
}
private static int GetDirByPipe(int x, int y, int dir) {
char pipe = board[x][y];
if (pipe == '+') {
return dir;
}
if (dir == 0) {
if (pipe == '1')
dir = 1;
else if (pipe == '4')
dir = 3;
else if (pipe == '-' || pipe == '2' || pipe == '3')
dir = -1;
} else if (dir == 1) {
if (pipe == '3')
dir = 0;
else if (pipe == '4')
dir = 2;
else if (pipe == '|' || pipe == '1' || pipe == '2')
dir = -1;
} else if (dir == 2) {
if (pipe == '2')
dir = 1;
else if (pipe == '3')
dir = 3;
else if (pipe == '-' || pipe == '1' || pipe == '4')
dir = -1;
} else if (dir == 3) {
if (pipe == '1')
dir = 2;
else if (pipe == '2')
dir = 0;
else if (pipe == '|' || pipe == '3' || pipe == '4')
dir = -1;
}
return dir;
}
private static boolean IsOutBound(int nx, int ny) {
return nx <= 0 || ny <= 0 || nx > N || ny > M;
}
}
리뷰
문제의 내용에 비해 상당히 귀찮은(?) 문제였던 것 같습니다. 가스의 흐름, 블록의 모양에 따라 상당히 많은 분기문을 작성해야 했습니다.
SW 0년차 개발자입니다.