프로그래밍/기타 문제풀이
[BOJ 1938] 통나무 옮기기
kkalgo
2023. 5. 9. 08:52
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문
www.acmicpc.net
- 통나무는 UP, DOWN, LEFT, RIGHT, ROTATE 가능하다.
- 주어진 문제의 크기는 50 * 50 배열의 크기가 최대이므로 bfs 탐색시 문제 없음
* 여기서 기둥이 가로방향인지, 세로방향으로 놓여져있는지 까지 별도 확인하기 위해 [50][50][2] 크기 방문배열 필요
* 즉 최대 5000번의 탐색
- 문제 아이디어
1. Coordi 클래스 선언 : 기둥의 중심좌표 x, y와 현재 기둥이 가로인지, 세로인지를 확인할 direction 변수 총 3개
2. 기둥의 시작점과 도착지점의 좌표를 구한다.
3. bfs로 UP, DOWN, LEFT, RIGHT, ROTATE의 경우를 방향에 따라 탐색한다.
- visited[10][10][0]이 true라는 것은 10행 10열에서 가로로 놓인 상태의 기둥은 방문했음을 의미
- visited[10][10][1]이 true라는 것은 10행 10열에서 세로로 놓인 상태의 기둥은 방문했음을 의미
* 즉, 방향에 따라 up, down, left, right, rotate에 대한 것을 경우의 수로 나누고 bfs를 탐색하는 문제임.
* 경우의 수 나눈 주석을 참고합니다
/*
* 1. class 정의 : Coordi
* - x, y, direction
*
* 2. 필요 자료구조 visited[n][n][2] // 해당 중심점에 가로, 세로방향으로 방문했는지 안했는지 체크.
*
*
* 3. method 정의 : up, down, left, right, toggle
*
*
* 4. bfs 기저조건
* - Coordi End와 같은 상태일 경우 return
*
* - 위의 기저조건을 만나지 못하는 경우는 return 0
*
*
* 1) direction이 0, 가로인 경우
* 가) up
* X - 1이 0보다 크거나 같은 경우
* 반복문 : Y-1 ~ Y+1까지 1 없으면 ok
*
* 나) down
* X + 1이 n보다 작은 경우
* 반복문 : Y-1 ~ Y+1까지 1 없으면 ok
*
* 다) left
* Y - 2가 0보다 크거나 같은 경우
* Y - 2 지점이 1이 아니면 ok
*
* 라) right
* Y + 2가 n보다 작은 경우
* Y + 2 지점이 1이 아니면 ok
*
* 마) rotate
* x -1이 0보다 크고 x + 1이 n보다 작으며
* y -1이 0보다 크고 y + 1이 n보다 작으면
*
* for (int i = x-1; i <= x+1; i++)
* for (int j= y-1; j <= y+1; j++)
* arr[i][j]에 1이 없으면 ok
*
* // 메소드 분리
*
*
* 2) direction이 1, 세로인 경우
* 가) up
* X - 2가 0보다 크거나 같은 경우
* X - 2 지점이 1이 아니면 ok
*
* 나) down
* X + 2가 n보다 작은 경우
* X + 2 지점이 1이 아니면 OK
*
* 다) left
* Y - 1이 0보다 크거나 같은 경우
* 반복문 : X -1 ~ X +1까지 1 없으면 OK
*
* 라) right
* Y + 1이 n보다 작은 경우
* 반복문 : X - 1 ~ X + 1까지 1 없으면 OK
*
* 마) rotate
* x -1이 0보다 크고 x + 1이 n보다 작으며
* y -1이 0보다 크고 y + 1이 n보다 작으면
*
* for (int i = x-1; i <= x+1; i++)
* for (int j= y-1; j <= y+1; j++)
* arr[i][j]에 1이 없으면 ok
*
*
*/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
public class Main {
static int n; // n * n 배열
static char[][] arr; // 입력받을 배열
static class Coordi {
int x; // x좌표
int y; // y좌표
int direction; // 방향 입력
public Coordi(int x, int y, int direction) {
super();
this.x = x;
this.y = y;
this.direction = direction;
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
n = Integer.parseInt(br.readLine());
arr = new char[n][n];
String str;
for (int i=0; i<n; i++) {
str = br.readLine();
for (int j=0; j<n; j++) {
arr[i][j] = str.charAt(j);
}
}
Coordi start = Check('B'); // 시작점 확인
Coordi end = Check('E'); // 종료점 확인
System.out.println(bfs(start,end));
}
private static int bfs(Coordi start, Coordi end) {
boolean [][][]visited = new boolean[n][n][2];
Queue<Coordi> q = new ArrayDeque<>();
q.add(start);
Coordi temp;
int cnt = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int t=0; t < size; t++) {
temp = q.poll();
if (temp.x == end.x && temp.y == end.y && temp.direction == end.direction) { // 도착지점이라면 반환한다.
return cnt;
}
if (visited[temp.x][temp.y][temp.direction]) continue;
visited[temp.x][temp.y][temp.direction] = true; // 해당 정점 방문처리
if (temp.direction == 0) { // 가로 방향인 경우
// 1. up
if (temp.x -1 >= 0 && !visited[temp.x-1][temp.y][0]) {
if (RowChangeThreePillar(temp.x-1,temp.y,0)) {
q.add(new Coordi(temp.x-1,temp.y,0));
}
}
// 2. down
if (temp.x + 1 < n && !visited[temp.x+1][temp.y][0]) {
if (RowChangeThreePillar(temp.x+1,temp.y,0)) {
q.add(new Coordi(temp.x+1,temp.y,0));
}
}
// 3. left
if (temp.y - 2 >= 0 && !visited[temp.x][temp.y-1][0]) {
if (arr[temp.x][temp.y-2] != '1') {
q.add(new Coordi(temp.x,temp.y-1,0));
}
}
// 4. right
if (temp.y +2 < n && !visited[temp.x][temp.y+1][0]) {
if (arr[temp.x][temp.y+2] != '1') {
q.add(new Coordi(temp.x,temp.y+1,0));
}
}
// 5. rotate
if (temp.x-1 >= 0 && temp.x+1 < n && temp.y-1 >= 0 && temp.y+1 < n) {
if (Rotate(temp.x,temp.y,temp.direction)) {
q.add(new Coordi(temp.x,temp.y,1));
}
}
}
else if (temp.direction == 1) {
// 1. up
if (temp.x-2 >= 0 && !visited[temp.x-1][temp.y][1]) {
if (arr[temp.x-2][temp.y] != '1') {
q.add(new Coordi(temp.x-1,temp.y,1));
}
}
// 2. down
if (temp.x+2 < n && !visited[temp.x+1][temp.y][1]) {
if (arr[temp.x+2][temp.y] != '1') {
q.add(new Coordi(temp.x+1,temp.y,1));
}
}
// 3. left
if (temp.y-1 >= 0 && !visited[temp.x][temp.y-1][1]) {
if (ColChangeThreePillar(temp.x,temp.y-1,1)) {
q.add(new Coordi(temp.x,temp.y-1,1));
}
}
// 4. right
if (temp.y+1 < n && !visited[temp.x][temp.y+1][1]) {
if (ColChangeThreePillar(temp.x,temp.y+1,1)) {
q.add(new Coordi(temp.x,temp.y+1,1));
}
}
// 5. rotate
if (temp.x-1 >= 0 && temp.x+1 < n && temp.y-1 >= 0 && temp.y+1 < n) {
if (Rotate(temp.x,temp.y,1)) {
q.add(new Coordi(temp.x,temp.y,0));
}
}
}
}
cnt++;
}
return 0;
}
private static boolean RowChangeThreePillar(int x, int y, int direction) { //가로일 때 기둥 3개를 옮기는 작업
for (int i= y-1; i <=y+1; i++) {
if (arr[x][i] == '1') return false;
}
return true;
}
private static boolean ColChangeThreePillar(int x, int y, int direction) { //세로일 때 기둥 3개를 옮기는 작업
for (int i= x-1; i <= x+1; i++) {
if (arr[i][y] == '1') return false;
}
return true;
}
private static boolean Rotate(int x, int y, int direction) { // 회전은 가로 세로 모두 동일하므로 공유
for (int i= x-1; i<= x+1; i++) {
for (int j= y-1; j <= y+1; j++) {
if (arr[i][j] == '1') return false;
}
}
return true;
}
private static Coordi Check(char c) { // 시작점, 도착지점 체크용 메서드 분리
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (arr[i][j] == c){
if (j + 1 < n && arr[i][j+1] == c) {
return new Coordi(i,j+1,0);
}
else return new Coordi(i+1,j,1);
}
}
}
return null;
}
}