반응형
11-14 12:35
- Today
- Total
Link
개발하는 고라니
[백준] 1938번 : 통나무 옮기기 본문
반응형
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사
www.acmicpc.net
[BFS]
차근차근 접근하면 결코 어렵지는 않은 문제인 것 같다. 다만 인덱스 범위나 조건처리 때문에 코드량이 길어지다보니 실수를 연발할 수 있는 여지가 다분하다.
우선 나의 접근법을 말해보자면, 가장 먼저 해당 정점을 방문했는지에 관한 것을 어떻게 처리했는가? 이다.
통나무의 길이는 3으로 고정되어있고, 대각선은 놓을 수 없으므로 통나무의 중간 지점을 가지고 방문 처리를 했다.
그런데 통나무는 수직으로 놓을 수 있고, 수평으로 놓을 수 있으므로 방향에 따라 방문을 최대 2번까지 할 수 있으므로
boolean[][] visit = new boolean[51][51][2];
로 주었다.
상하좌우 옮길 때는 굳이 말을 안해도 다 알것으로 기대된다. 옮기려고 하는 곳에 '1'이 있거나, 범위를 넘어서지 않는 조건처리만 해주면 된다.
남은 것은 회전(Rotate)일 때인데, 통나무의 가운데를 기준으로 상하좌우, 대각선 칸 모두 '1'이 있어선 안된다. 즉 회전하는 공간을 마련해주어야 한다. 나는 이를 '수평'일 때와 '수직'일 때를 나누어 회전시키도록 했다.
static boolean rotate(Point[] p, int dir) { //dir -> 0: 수직, 1: 수평
if(p[1].y-1 < 1 || p[1].y+1 > n || p[1].x-1 < 1 || p[1].x+1 > n)
return false;
for(int a=0; a<8; a++)
if(map[p[1].y+Y[a]][p[1].x+X[a]] == '1')
return false;
if(dir == 0){
p[0].y++;
p[0].x--;
p[2].y--;
p[2].x++;
}
else{
p[0].y--;
p[0].x++;
p[2].y++;
p[2].x--;
}
return true;
}특이하게도 boolean 반환형인데, 이는 회전하는 도중 '1'을 만나거나, 지정된 범위를 벗어나면 false를 주어 더이상 진행되지 않도록 했다.
이 문제는 그리 어렵진 않으나 역시 인덱스 범위에 따른 에러처리가 관건인 문제라고 생각된다. 적절하게 함수로 빼서 가독성을 높이거나, 세심하게 주의를 기울이면 해결할 수 있다.
# 50 x 50 예시
BBB00000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000EEE
# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
/* Class Def */
static class Point{
int y, x;
public Point(int yy, int xx){
y=yy;
x=xx;
}
}
static class Log{
Point[] p;
int dir, move; //0 수직 1 수평
public Log(Point[] logs, int d, int m){
p=logs;
dir=d;
move=m;
}
}
/* Setting */
static int n;
static int[] Y={-1,1,0,0,-1,-1,1,1}, X={0,0,-1,1,-1,1,-1,1};
static char[][] map = new char[51][51];
static boolean[][][] visit = new boolean[51][51][2]; //0: 수직 1: 수평
/* Methods Def */
static boolean up(Point[] p){
for(Point log:p)
if(log.y < 1 || map[log.y][log.x] == '1')
return false;
return true;
}
static boolean down(Point[] p){
for(Point log:p)
if(log.y > n || map[log.y][log.x] == '1')
return false;
return true;
}
static boolean left(Point[] p){
for(Point log:p)
if(log.x < 1 || map[log.y][log.x] == '1')
return false;
return true;
}
static boolean right(Point[] p){
for(Point log:p)
if(log.x > n || map[log.y][log.x] == '1')
return false;
return true;
}
static boolean rotate(Point[] p, int dir) {
if(p[1].y-1 < 1 || p[1].y+1 > n || p[1].x-1 < 1 || p[1].x+1 > n)
return false;
for(int a=0; a<8; a++)
if(map[p[1].y+Y[a]][p[1].x+X[a]] == '1')
return false;
if(dir == 0){
p[0].y++;
p[0].x--;
p[2].y--;
p[2].x++;
}
else{
p[0].y--;
p[0].x++;
p[2].y++;
p[2].x--;
}
return true;
}
static boolean isRight(Point p, int y, int x){
if(p.y+y < 1 || p.y+y > n || p.x+x < 1 || p.x+x > n) return false;
return true;
}
static int BFS(Point[] s){
Queue<Log> Q = new LinkedList<>();
int dir_s = s[0].x == s[1].x? 0:1;
visit[s[1].y][s[1].x][dir_s] = true;
Q.add(new Log(s, dir_s, 0));
while(!Q.isEmpty()){
Log log = Q.poll();
Point[] cur = log.p;
int dir = log.dir;
int move = log.move;
if(map[cur[0].y][cur[0].x] == 'E' && map[cur[2].y][cur[2].x] == 'E')
return move;
/* 위쪽 */
if(isRight(cur[1], -1, 0) && !visit[cur[1].y-1][cur[1].x][dir]) {
Point[] up = new Point[3];
for(int i=0; i<3; i++)
up[i] = new Point(cur[i].y-1, cur[i].x);
if (up(up)) {
visit[up[1].y][up[1].x][dir] = true;
Q.add(new Log(up, dir, move + 1));
}
}
/* 아래쪽 */
if(isRight(cur[1], 1, 0) && !visit[cur[1].y+1][cur[1].x][dir]) {
Point[] down = new Point[3];
for (int i = 0; i < 3; i++)
down[i] = new Point(cur[i].y+1, cur[i].x);
if (down(down)) {
visit[down[1].y][down[1].x][dir] = true;
Q.add(new Log(down, dir, move + 1));
}
}
/* 왼쪽 */
if(isRight(cur[1], 0, -1) && !visit[cur[1].y][cur[1].x-1][dir]) {
Point[] left = new Point[3];
for (int i = 0; i < 3; i++)
left[i] = new Point(cur[i].y, cur[i].x-1);
if (left(left)) {
visit[left[1].y][left[1].x][dir] = true;
Q.add(new Log(left, dir, move + 1));
}
}
/* 오른쪽 */
if(isRight(cur[1], 0, 1) && !visit[cur[1].y][cur[1].x+1][dir]) {
Point[] right = new Point[3];
for (int i = 0; i < 3; i++)
right[i] = new Point(cur[i].y, cur[i].x+1);
if (right(right)) {
visit[right[1].y][right[1].x][dir] = true;
Q.add(new Log(right, dir, move + 1));
}
}
/* 회전 */
int nDir = dir == 0 ? 1 : 0;
if(!visit[cur[1].y][cur[1].x][nDir]) {
Point[] rotate = new Point[3];
for (int i = 0; i < 3; i++)
rotate[i] = new Point(cur[i].y, cur[i].x);
if (rotate(rotate, dir)) {
visit[rotate[1].y][rotate[1].x][nDir] = true;
Q.add(new Log(rotate, nDir, move + 1));
}
}
}
return 0;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int idx = 0;
Point[] log = new Point[3];
for (int i = 1; i <= n; i++) {
char[] strs = br.readLine().toCharArray();
for (int j = 1; j <= n; j++) {
map[i][j] = strs[j - 1];
if (map[i][j] == 'B')
log[idx++] = new Point(i, j);
}
}
System.out.println(BFS(log));
}
}반응형
'Programming > 백준' 카테고리의 다른 글
| [백준] 2562번 : 최댓값 (0) | 2021.05.01 |
|---|---|
| [백준] 16929번 : Two Dots (0) | 2021.05.01 |
| [백준] 11021번 : A + B - 7 (0) | 2021.04.28 |
| [백준] 16932번 : 모양 만들기 (0) | 2021.04.15 |
| [백준] 16973번 : 직사각형 탈출 (0) | 2021.04.15 |
Comments