본문 바로가기

알고리즘 관련/BOJ

1938 통나무 옮기기

문제: https://www.acmicpc.net/problem/1938

 

1938번: 통나무 옮기기

첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문

www.acmicpc.net

통나무 옮기는 방향을 상하좌우, 회전 5가지로 구분할 수 있다. 각각의 방향으로 이동한 상태를 기억하기 위해 BFS를 사용하기 적합하다 판단했고, 다음 상태로 이동하기 전에 나무가 있는지, 범위를 벗어나지 않는지를 확인하여 탐색하면 답을 구할 수 있다.

범위를 벗어나는 경우를 좀 더 쉽게 처리하기 위해 기존의 맵을 감싸는 영역을 나무로 저장하도록 했다.

import java.io.*;
import java.util.*;
class Node{
  int r, c, d;
  public Node(int r, int c, int d){
    this.r = r;
    this.c = c;
    this.d = d;
  }
}
public class Main {
  public static int N;
  public static char[][] arr;
  public static int[][][] visit;
  public static Node Start, End;
  public static int Dir[][] = {{1, 0, 0}, {-1, 0, 0}, {0, 1, 0}, {0, -1, 0}, {0, 0, 1}};
  public static void init(){
    for(int i = 1; i <= N; i++){
      for(int j = 1; j <= N; j++){
        if(arr[i][j] == 'B'){
          if(arr[i - 1][j] == 'B' && arr[i + 1][j] == 'B')
            Start = new Node(i, j, 1);
          else if(arr[i][j - 1] == 'B' && arr[i][j + 1] == 'B')
            Start = new Node(i, j, 0);
        }
        else if(arr[i][j] == 'E'){
          if(arr[i - 1][j] == 'E' && arr[i + 1][j] == 'E')
            End = new Node(i, j, 1);
          else if(arr[i][j - 1] == 'E' && arr[i][j + 1] == 'E')
            End = new Node(i, j, 0);
        }
      }
    }
  }
  public static boolean canRotate(int r, int c){
    boolean tree = false;
    for(int i = -1; i <= 1; i++){
      for(int j = -1; j <= 1; j++){
        if(arr[r + i][c + j] == '1'){
          tree = true;
        }
      }
    }
    return tree == false;
  }
  public static boolean canShift(int r, int c, int d){
    boolean tree = false;
    //밀었을 때 나무가 하나라도 있으면 실패
    if(d == 0){ //가로
      for(int i = -1; i <= 1; i++){
        if(arr[r][c + i] == '1') {
          tree = true;
        }
      }
    }
    else{ //세로
      for(int i = -1; i <= 1; i++){
        if(arr[r + i][c] == '1'){
          tree = true;
        }
      }
    }
    return tree == false;
  }
  public static void bfs(){
    Queue<Node> q = new ArrayDeque<>();
    q.add(Start);
    int nr, nc, nd;
    while(!q.isEmpty()){
      Node cur = q.poll();
      //5방향 탐색 (상, 하, 좌, 우, 회전)
      for(int i = 0; i < Dir.length; i++){
        nr = cur.r + Dir[i][0];
        nc = cur.c + Dir[i][1];
        nd = (cur.d + Dir[i][2]) % 2; //방향 전환
        //범위 초과
        if(nr <= 0 || nc <= 0 || nr > N || nc > N)
          continue;
          //회전이 가능한지 체크
        else if(cur.d != nd && !canRotate(nr, nc))
          continue;
          //이동이 가능한지 체크
        else if(!canShift(nr, nc, nd))
          continue;

        if(visit[nr][nc][nd] == 0){
          visit[nr][nc][nd] += visit[cur.r][cur.c][cur.d] + 1;
          q.add(new Node(nr, nc, nd));
        }
      }
    }
  }
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    arr = new char[N + 2][N + 2];
    visit = new int[N + 2][N + 2][2];
    for(int i = 0; i <= N + 1; i++)
      for(int j = 0; j <= N + 1; j++)
        arr[i][j] = '1';
    for(int i = 1; i <= N; i++){
      String str = br.readLine();
      for(int j = 0; j < N; j++){
        arr[i][j + 1] = str.charAt(j);
      }
    }
    init();
    bfs();
    System.out.println(visit[End.r][End.c][End.d]);
  }
}

'알고리즘 관련 > BOJ' 카테고리의 다른 글

11062 카드 게임  (0) 2022.01.06
22254 공정 컨설턴트 호석  (0) 2022.01.06
9205 맥주 마시면서 걸어가기  (0) 2021.12.27
16987 계란으로 계란치기  (0) 2021.12.27
16197 두 동전  (0) 2021.12.22