1600번) 말이 되고픈 원숭이

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

해당 문제를 푸는데 어려움이 있었습니다.

초기 코드를 1시간 정도 작성하고, 제출한 결과 정답이 중간정도 맞다가 틀렸습니다.

이후 30분 동안, 알고리즘을 생각했습니다.

아무리 생각해도, 알고리즘(로직)은 맞는데, 정답은 중간정도 맞다가 틀렸다고 나왔네요.

코드를 계속 수정하고, 수정하고 수정했는데도 틀렸습니다.

이 문제는 다음날(4월 11일) 문제를 다시 읽으며 해결할 수 있었어요.

다른 문제와는 다르게,

입력에서 map의 "가로길이"부터 주어지는것을 발견했습니다.

으..............................

시험용 BFS공부 중이기 때문에, 클린 코딩보다는

하드 코딩 중인데, 덕분에 코드를 어느정도 다듬었네요.

또......... 문제를 제대로 읽자라는 교훈을 얻었습니다.

2018년 4월 11일 - 다듬은 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Q1600 { static int horseMaxCount, ySize, xSize; static long result = -1; static int[][] map; static boolean[][][] isVisit; static int[] moveY = new int[]{-1, 0, 1, 0, -2, -1, 1, 2, 2, 1, -1, -2}; static int[] moveX = new int[]{0, 1, 0, -1, 1, 2, 2, 1, -1, -2, -2, -1}; public static void main(String[] args) { Scanner sc = new Scanner(System.in); horseMaxCount = sc.nextInt(); xSize = sc.nextInt(); ySize = sc.nextInt(); map = new int[ySize][xSize]; isVisit = new boolean[horseMaxCount+1][ySize][xSize]; for (int i = 0 ; i < ySize; i++) { for (int j = 0 ; j < xSize; j++) { map[i][j] = sc.nextInt(); } } if (ySize == 1 && xSize == 1) { System.out.println(0); return; } //BFS startBfs(); System.out.println(result); } static void startBfs() { Queue<Position> queue = new LinkedList<Position>(); queue.add(new Position(0, 0, 0, 0)); while (!queue.isEmpty()) { Position nowPosition = queue.poll(); int nowY = nowPosition.getY(); int nowX = nowPosition.getX(); int nowHorseCount = nowPosition.getHorseCount(); long nextCount = nowPosition.getCount()+1;  int tempY, tempX; for (int i = 0; i < 4; i++) { tempY = nowY+moveY[i]; tempX = nowX+moveX[i]; if (0 <= tempY && tempY < ySize && 0 <= tempX && tempX < xSize && map[tempY][tempX] == 0 && !isVisit[nowHorseCount][tempY][tempX]) { // System.out.println("말처럼 " + tempY + ", " + tempX + " / " + nowHorseCount); if (tempY == ySize-1 && tempX == xSize-1) { if (result == -1 || result > nextCount) { result = nextCount; return; } } isVisit[nowHorseCount][tempY][tempX] = true; queue.add(new Position(tempY, tempX, nowHorseCount, nextCount)); } } if (nowHorseCount < horseMaxCount) { int nextHorseCount = nowHorseCount+1; for (int i = 4; i < 12; i++) { tempY = nowY+moveY[i]; tempX = nowX+moveX[i]; if (0 <= tempY && tempY < ySize && 0 <= tempX && tempX < xSize && map[tempY][tempX] == 0 && !isVisit[nextHorseCount][tempY][tempX]) { // System.out.println("말처럼 " + tempY + ", " + tempX + " / " + nextHorseCount); if (tempY == ySize-1 && tempX == xSize-1) { if (result == -1 || result > nextCount) { result = nextCount; return; } } isVisit[nextHorseCount][tempY][tempX] = true; queue.add(new Position(tempY, tempX, nextHorseCount, nextCount)); } } } } } } class Position { private int y, x, horseCount; private long count; public Position(int y, int x, int horseCount, long count) { this.y = y; this.x = x; this.horseCount = horseCount; this.count = count; } public int getY() { return y; } public int getX() { return x; } public int getHorseCount() { return horseCount; } public long getCount() { return count; } }