14503번) 로봇 청소기

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

굉장히 쉬울것이라 생각했는데, 시간 좀 걸렸습니다.

어려운 부분 : 명시된 로봇청소기 알고리즘 제대로 이해하기.

2018년 4월 6일 - 다듬지 않은 시험 코드 (소요시간 : 1시간 32분) package samsung; import java.util.Scanner; public class Q14503 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int ySize = sc.nextInt(); int xSize = sc.nextInt(); int[][] map = new int[ySize][xSize]; int nowY = sc.nextInt(); int nowX = sc.nextInt(); int nowDirection = sc.nextInt(); for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { map[i][j] = sc.nextInt(); } } //청소 안한 빈 칸은 0, 벽은 1로, 청소한 칸은 2. //   0 // 3   1 //   2 int count = 0; int result = 0; while(true) { // System.out.println(); // for (int i = 0; i < ySize; i++) { // for (int j = 0; j < xSize; j++) { // int temp = map[i][j]; // if (temp == 1) { // System.out.print("# "); // } else if (temp == 2) { // System.out.print("■ "); // } else { // System.out.print("□ "); // } // } // System.out.println(); // } // System.out.print("\n" + count); count += 1; //현재 위치 청소 if (map[nowY][nowX] == 0) { map[nowY][nowX] = 2; result += 1; // System.out.print("  청소"); } //방향 전환 int tempNowDirection = getRotation(nowDirection); // int tempY = nowY, tempX = nowX; switch (tempNowDirection) { case 0 : tempY -= 1; break; case 1 : tempX += 1; break; case 2 : tempY += 1; break; case 3 : tempX -= 1; break; } if (map[tempY][tempX] == 0) { //한칸 전진 // System.out.print("  전진"); nowY = tempY; nowX = tempX; nowDirection = tempNowDirection; continue; } //청소할 공간 있으면 회전만 한다. if (map[nowY-1][nowX] == 0 || map[nowY+1][nowX] == 0 || map[nowY][nowX-1] == 0 || map[nowY][nowX+1] == 0) { // System.out.print("  회전  "); nowDirection = tempNowDirection; continue; } tempY = nowY; tempX = nowX; switch (nowDirection) { case 0 : tempY += 1; break; case 1 : tempX -= 1; break; case 2 : tempY -= 1; break; case 3 : tempX += 1; break; } if (map[tempY][tempX] == 1) { // System.out.print("  종료  "); System.out.print(result); // // // System.out.println(); // for (int i = 0; i < ySize; i++) { // for (int j = 0; j < xSize; j++) { // int temp = map[i][j]; // if (temp == 1) { // System.out.print("# "); // } else if (temp == 2) { // System.out.print("■ "); // } else { // System.out.print("□ "); // } // } // System.out.println(); // } return; } else { nowY = tempY; nowX = tempX; // System.out.print("  후진"); } } } static int getRotation(int nowDirection) { nowDirection -= 1; if (nowDirection == -1) { nowDirection = 3; } return nowDirection; } }

2018년 4월 6일 - 필요 없는거 지운 코드 (다듬기 귀찮아여) import java.util.Scanner; public class Q14503 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int ySize = sc.nextInt(); int xSize = sc.nextInt(); int[][] map = new int[ySize][xSize]; int nowY = sc.nextInt(); int nowX = sc.nextInt(); int nowDirection = sc.nextInt(); for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { map[i][j] = sc.nextInt(); } } //청소 안한 빈 칸은 0, 벽은 1로, 청소한 칸은 2. int result = 0; while(true) { //현재 위치 청소 if (map[nowY][nowX] == 0) { map[nowY][nowX] = 2; result += 1; } //방향 전환 int tempNowDirection = getRotation(nowDirection); //왼쪽 칸 계산 int tempY = nowY, tempX = nowX; switch (tempNowDirection) { case 0 : tempY -= 1; break; case 1 : tempX += 1; break; case 2 : tempY += 1; break; case 3 : tempX -= 1; break; } //왼쪽칸을 청소할 수 있으면 왼쪽칸으로 전진 if (map[tempY][tempX] == 0) { nowY = tempY; nowX = tempX; nowDirection = tempNowDirection; continue; } //상, 하, 좌, 우  총 4개의 칸 중 청소할 칸이 있으면 회전한다. if (map[nowY-1][nowX] == 0 || map[nowY+1][nowX] == 0 || map[nowY][nowX-1] == 0 || map[nowY][nowX+1] == 0) { nowDirection = tempNowDirection; continue; } //후진 칸 계산 tempY = nowY; tempX = nowX; switch (nowDirection) { case 0 : tempY += 1; break; case 1 : tempX -= 1; break; case 2 : tempY -= 1; break; case 3 : tempX += 1; break; } //후진할 곳이 없으면 종료 if (map[tempY][tempX] == 1) { System.out.print(result); return; } nowY = tempY; nowX = tempX; } } static int getRotation(int nowDirection) { nowDirection -= 1; if (nowDirection == -1) { nowDirection = 3; } return nowDirection; } static void showMap(int[][] map) { for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { int temp = map[i][j]; if (temp == 1) { System.out.print("# "); } else if (temp == 2) { System.out.print("■ "); } else { System.out.print("□ "); } } System.out.println(); } } }

로봇청소기를 보유하고 있어서 그런지,

꽤 재밌네요.

18년 4월 12일 - 다듬지 않은 코드 (소요시간 42분) import java.util.Scanner; public class Q14503 { static int ySize, xSize, count = 0; static int[][] map; static boolean[][] isCleanedMap; public static void main(String[] args) { Scanner sc = new Scanner(System.in); ySize = sc.nextInt(); xSize = sc.nextInt(); int nowY = sc.nextInt(); int nowX = sc.nextInt(); int nowDirection = sc.nextInt(); isCleanedMap = new boolean[ySize][xSize]; map = new int[ySize][xSize]; for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { int tempValue = sc.nextInt(); if (tempValue == 1) { isCleanedMap[i][j] = true; map[i][j] = 1; } } } startRobot(nowY, nowX, nowDirection); System.out.println(count); } static void startRobot(int y, int x, int direction) { // showMap(y, x, direction); if (!isCleanedMap[y][x]) { isCleanedMap[y][x] = true; count += 1; } //TODO 현재 사방이 막혔는지 확인 boolean isBack = getIsBack(y, x); if (isBack) { // System.out.println("사방이 막혔다"); int backPosition[] = getBackPosition(y, x, direction); if (map[backPosition[0]][backPosition[1]] == 1) { return; } startRobot(backPosition[0], backPosition[1], direction); return; } direction = getNextDirection(direction); int[] nextPosition = getNextPosition(y, x, direction); if (0 <= nextPosition[0] && nextPosition[0] < ySize && 0 <= nextPosition[1] && nextPosition[1] < xSize && !isCleanedMap[nextPosition[0]][nextPosition[1]]) { startRobot(nextPosition[0], nextPosition[1], direction); return; } startRobot(y, x, direction); } static boolean getIsBack(int y, int x) { int[] moveY = {-1, 0, 1, 0}; int[] moveX = {0, 1, 0, -1}; for (int i = 0; i < 4; i++) { int tempY = y+moveY[i], tempX = x+moveX[i]; if (0 <= tempY && tempY < ySize && 0 <= tempX && tempX < xSize && !isCleanedMap[tempY][tempX]) { return false; } } return true; } static int getNextDirection(int nowDirection) { nowDirection -= 1; if (nowDirection == -1) { nowDirection = 3; } return nowDirection; } static int[] getNextPosition(int y, int x, int direction) { int tempY = y, tempX = x; switch(direction) { case 0 : tempY -= 1; break; case 1 : tempX += 1; break; case 2 : tempY += 1; break; case 3 : tempX -= 1; break; } return new int[]{tempY, tempX}; } static int[] getBackPosition(int y, int x, int direction) { int tempY = y, tempX = x; switch(direction) { case 0 : tempY += 1; break; case 1 : tempX -= 1; break; case 2 : tempY -= 1; break; case 3 : tempX += 1; break; } return new int[]{tempY, tempX}; } static void showMap(int y, int x, int direction) { for (int i = 0; i < ySize; i++) { for (int j = 0; j < xSize; j++) { if (i == y && j == x) { switch (direction) { case 0 : System.out.print("^ "); break; case 1 : System.out.print("> "); break; case 2 : System.out.print("v "); break; case 3 : System.out.print("< "); break; } } else if (map[i][j] == 1) { System.out.print("1 "); } else if (isCleanedMap[i][j]) { System.out.print("□ "); } else { System.out.print("■ "); } } System.out.println(); } System.out.println(); } }