1939번) 통나무 옮기기

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

14503.로봇청소기와 13460.구슬탈출2 의 문제를 합한 느낌이네요.

이동시키지만, 세개의 나무가 이동해야 된다는 점에서 까다로웠어요.

올림피아드 고등부 2번 문제!!!..............

BFS로 풀었습니다.

대나무의 center 좌표와, 현재 가로, 세로상태, 카운트를 가지는 객체를 만들어줬고,

상, 하, 좌, 우, 회전이 가능할 경우(공간이 있을 경우) 해당 동작을 수행하도록 구현했어요.

처음에는 처음에는 대나무 세좌표를 모드 저장했지만, 객체 복사 문제로, 센터 좌표값만 저장하도록 했습니다.

불가능 할 경우에는 0이 나오도록 구현을 해야해요.

2018년 4월 10일 - 다듬지 않은 코드 (소요시간 : 1시간 42분) import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Q1938 { static int[][] map; static int size, result = 0; static Things goal; public static void main(String[] args) { Scanner sc = new Scanner(System.in); size = sc.nextInt(); map = new int[size][size]; Things tree = new Things(); int treeNum = 0; int goalNum = 0; for (int i = 0 ; i < size; i++) { String tempString = sc.next(); for (int j = 0; j < size; j++) { char temp = tempString.charAt(j); if (temp == '1') { map[i][j] = 1; } else if (temp == 'B') { if (treeNum == 0) { if (j+1 < size && tempString.charAt(j+1) == 'B') { tree = new Things(i, j+1, 1, -1); } else { tree = new Things(i+1, j, 0, -1); } treeNum += 1; } } else if (temp == 'E') { if (goalNum == 0) { if (j+1 < size && tempString.charAt(j+1) == 'E') { goal = new Things(i, j+1, 1, 0); } else { goal = new Things(i+1, j, 0, 0); } goalNum += 1; } } } } //BFS isVisit = new boolean[2][size][size]; searchBfs(tree); System.out.println(result); } static boolean[][][] isVisit; //0은 버티컬, 1은 호리젠탈 static void searchBfs(Things tree) { Queue<Things> queue = new LinkedList<Things>(); queue.add(tree); while (!queue.isEmpty()) { Things nowTree = queue.poll(); int centerY = nowTree.getCenterY(); int centerX = nowTree.getCenterX(); int rotation = nowTree.getRotation(); if (isVisit[rotation][centerY][centerX]) { continue; } isVisit[rotation][centerY][centerX] = true; int count = nowTree.getCount()+1; //같은지 확인 if (centerY == goal.getCenterY() && centerX == goal.getCenterX() && rotation == goal.getRotation()) { result = count; return; } // System.out.println("센터 " + centerY + " / " + centerX); if (rotation == 0) { //버티컬이면 //상 if (0 <= centerY-2 && map[centerY-2][centerX] == 0) { Things tempTree = new Things(centerY-1, centerX, rotation, count); queue.add(tempTree); } //하 if (centerY+2 < size && map[centerY+2][centerX] == 0) { Things tempTree = new Things(centerY+1, centerX, rotation, count); queue.add(tempTree); } //좌 if (0 <= centerX-1 && map[centerY-1][centerX-1] == 0 && map[centerY][centerX-1] == 0 && map[centerY+1][centerX-1] == 0) { Things tempTree = new Things(centerY, centerX-1, rotation, count); queue.add(tempTree); } //우 if (centerX+1 < size && map[centerY-1][centerX+1] == 0 && map[centerY][centerX+1] == 0 && map[centerY+1][centerX+1] == 0) { Things tempTree = new Things(centerY, centerX+1, rotation, count); queue.add(tempTree); } //회전 if (0 <= centerX-1 && centerX+1 < size && map[centerY-1][centerX-1] == 0 && map[centerY][centerX-1] == 0 && map[centerY+1][centerX-1] == 0 && map[centerY-1][centerX+1] == 0 && map[centerY][centerX+1] == 0 && map[centerY+1][centerX+1] == 0) { Things tempTree = new Things(centerY, centerX, 1, count); queue.add(tempTree); } } else { //호리즌탈이면 //상 if (0 <= centerY-1 && map[centerY-1][centerX-1] == 0 && map[centerY-1][centerX] == 0 && map[centerY-1][centerX+1] == 0) { Things tempTree = new Things(centerY-1, centerX, rotation, count); queue.add(tempTree); } //하 if (centerY+1 < size && map[centerY+1][centerX-1] == 0 && map[centerY+1][centerX] == 0 && map[centerY+1][centerX+1] == 0) { Things tempTree = new Things(centerY+1, centerX, rotation, count); queue.add(tempTree); } //좌 if (0 <= centerX-2 && map[centerY][centerX-2] == 0) { Things tempTree = new Things(centerY, centerX-1, rotation, count); queue.add(tempTree); } //우 if (centerX+2 < size && map[centerY][centerX+2] == 0) { Things tempTree = new Things(centerY, centerX+1, rotation, count); queue.add(tempTree); } //회전 if (0 <= centerY-1 && centerY+1 < size && map[centerY-1][centerX-1] == 0 && map[centerY-1][centerX] == 0 && map[centerY-1][centerX+1] == 0 && map[centerY+1][centerX-1] == 0 && map[centerY+1][centerX] == 0 && map[centerY+1][centerX+1] == 0) { Things tempTree = new Things(centerY, centerX, 0, count); queue.add(tempTree); } } } } } class Things { private int centerY, centerX, rotation; //0(버티컬-세로), 1(호리즌-가로) private int count; public Things() {}; public Things(int centerY, int centerX, int rotation, int count) { this.centerY = centerY; this.centerX = centerX; this.rotation = rotation; this.count = count; } public int getCenterY() { return centerY; } public int getCenterX() { return centerX; } public int getRotation() { return rotation; } public int getCount() { return count; } }