https://www.acmicpc.net/problem/14503
아래와 같은 조건을 순서대로 진행하면서 코드를 작성하면 된다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
주의할 점은 graph[x][y]에서 y가 좌우, x가 상하로 움직인다는 것과 왼쪽 방향으로 탐색하기때문에 북쪽을 보고 있었다면 서쪽 방향을 탐색한다는 것이다.
또, b의 조건을 탐색할 때 왼쪽 방향에 청소할 공간이 없고, 동서남북 어딘가에 청소할 공간이 있어야 탐색해야 한다. 그렇지 않다면 c 조건으로 들어가지 못해 무한 루프에 빠지게 된다.
import java.io.*;
public class Main {
static int[] dx = {0, 0, -1, 1};
static int[] dy = {1, -1, 0, 0};
static boolean[][] visit;
static int n, m;
static int ans = 0;
static int[][] graph;
// 0은 북, 1은 동, 2는 남, 3은 서
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] first = br.readLine().split(" ");
n = Integer.parseInt(first[0]);
m = Integer.parseInt(first[1]);
graph = new int[n][m];
visit = new boolean[n][m];
String[] pos = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
String[] line = br.readLine().split(" ");
for (int j = 0; j < m; j++) {
graph[i][j] = Integer.parseInt(line[j]);
}
}
// 로봇 청소기 위치는 3
int x = Integer.parseInt(pos[0]);
int y = Integer.parseInt(pos[1]);
int direction = Integer.parseInt(pos[2]);
Robot robot = new Robot(x, y, direction);
//One:
int temp = 0;
while (true) {
/*System.out.println(robot.direction);
printG();*/
temp++;
cleanTile(robot.x, robot.y);
boolean checkTwoA = checkMove(robot);
if (checkTwoA)
continue;
boolean checkTwoB = checkB(robot);
if (checkTwoB)
continue;
boolean checkTwoC = checkC(robot);
if (checkTwoC)
continue;
boolean checkTwoD = checkFin(robot.x, robot.y, robot.direction);
if (checkTwoD)
break;
}
//printG();
bw.write(ans + "\n");
br.close();
bw.close();
}
private static void printG() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
System.out.print(graph[i][j] + " ");
System.out.println();
}
System.out.println("-----------------");
}
// 1번
private static void cleanTile(int x, int y) {
if (graph[x][y] == 0) {
graph[x][y] = 2;
ans++;
}
}
//2.a
private static boolean checkMove(Robot robot) {
int x = robot.x;
int y = robot.y;
int direction = robot.direction;
if (direction == 0) {
if (graph[x][y - 1] == 0) {
robot.direction = 3;
robot.y = y - 1;
return true;
}
} else if (direction == 1) {
if (graph[x - 1][y] == 0) {
robot.direction = 0;
robot.x = x - 1;
robot.y = y;
return true;
}
} else if (direction == 2) {
if (graph[x][y + 1] == 0) {
robot.direction = 1;
robot.y = y + 1;
return true;
}
} else if (direction == 3) {
if (graph[x + 1][y] == 0) {
robot.direction = 2;
robot.x = x + 1;
robot.y = y;
return true;
}
}
return false;
}
// 2.b
private static boolean checkB(Robot robot) {
int x = robot.x;
int y = robot.y;
int direction = robot.direction;
if (!(graph[x + 1][y] != 0 && graph[x - 1][y] != 0 && graph[x][y - 1] != 0 && graph[x][y + 1] != 0)) {
if (direction == 0) {
if (graph[x][y - 1] != 0) {
robot.direction = 3;
return true;
}
} else if (direction == 1) {
if (graph[x - 1][y] != 0) {
robot.direction = 0;
return true;
}
} else if (direction == 2) {
if (graph[x][y + 1] != 0) {
robot.direction = 1;
return true;
}
} else if (direction == 3) {
if (graph[x + 1][y] != 0) {
robot.direction = 2;
return true;
}
}
}
return false;
}
//2.c
private static boolean checkC(Robot robot) {
int x = robot.x;
int y = robot.y;
int direction = robot.direction;
if (graph[x + 1][y] != 0 && graph[x - 1][y] != 0 && graph[x][y - 1] != 0 && graph[x][y + 1] != 0) {
if (direction == 0) {
if (graph[x + 1][y] != 1) {
robot.x = x + 1;
robot.y = y;
return true;
}
} else if (direction == 1) {
if (graph[x][y - 1] != 1) {
robot.y = y - 1;
return true;
}
} else if (direction == 2) {
if (graph[x - 1][y] != 1) {
robot.x = x - 1;
robot.y = y;
return true;
}
} else if (direction == 3) {
if (graph[x][y + 1] != 1) {
robot.y = y + 1;
return true;
}
}
}
return false;
}
//2.d
private static boolean checkFin(int x, int y, int direction) {
if (graph[x + 1][y] != 0 && graph[x - 1][y] != 0 && graph[x][y - 1] != 0 && graph[x][y + 1] != 0) {
if (direction == 0) {
return graph[x + 1][y] == 1;
} else if (direction == 1) {
return graph[x][y - 1] == 1;
} else if (direction == 2) {
return graph[x - 1][y] == 1;
} else if (direction == 3) {
return graph[x][y + 1] == 1;
}
}
return false;
}
}
class Robot {
public int x;
public int y;
// 0은 북, 1은 동, 2는 남, 3은 서
public int direction;
public Robot(int x, int y, int direction) {
this.x = x;
this.y = y;
this.direction = direction;
}
}