출처
접근
- N, M <= 50, O(N^5) = 312,500,000 이므로 시간복잡도는 여유롭게 구현 가능합니다.
- 로봇 청소기의 이동 방식을 BFS로 구현했습니다.
다시 생각해보니 BFS형태가 아니더라도 구현 가능한데 습관적으로 BFS를 사용한 것 같습니다.
- 문제에서 주어진 방향설정이 중요합니다.
북(-1, 0), 동(0, 1), 남(1, 0), 서(0, -1)
- 친절하게 방의 둘레는 모두 벽(1)로 채워져 있기 때문에 ArrayIndexOutOfBoundsException1은 처리하지 않아도 됩니다.
풀이
package solving;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
/*
* N, M이 50 이하이므로, 시간복잡도와 메모리제한은 고려하지 않음
* [풀이]
* 로봇 청소기의 이동 방식을 bfs로 구현한다.
* 방향 : 북(-1, 0), 동(0, 1), 남(1, 0), 서(0, -1)
* 청소를 마치면 0 -> -1로 변경
* 로봇의 동작은 각각 별도의 메서드로 분리
*/
public class bj_14503_로봇_청소기 {
static int N;
static int M;
static int[][] room;
static int[] dr = {-1, 0, 1, 0};
static int[] dc = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
room = new int[N + 1][M + 1];
st = new StringTokenizer(br.readLine());
int[] start = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
int direction = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) room[i][j] = Integer.parseInt(st.nextToken());
}
solve(start, direction);
}
private static void solve(int[] start, int direction) {
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{start[0], start[1], direction});
int count = 0;
while (!q.isEmpty()) {
int[] cur = q.poll();
int r = cur[0], c = cur[1], d = cur[2];
// 현재 칸이 청소되지 않은 경우
if (room[r][c] == 0) {
count++;
room[r][c] = -1;
}
// 주변 4칸 중 빈칸이 없을 경우
if (!findDirty(r, c)) {
int[] back = moveBack(r, c, d);
if (back == null) break;
q.offer(back);
}
// 주변 4칸 중 빈칸이 있을 경우
else {
for (int i = 0; i < 4; i++) {
d = d == 0 ? 3 : d == 3 ? 2 : d == 2 ? 1 : 0;
int[] forward = moveForward(r, c, d);
if (forward != null) {
q.offer(forward);
break;
}
}
}
}
System.out.println(count);
}
private static int[] moveForward(int r, int c, int nd) {
int nr = r + dr[nd];
int nc = c + dc[nd];
// 더이상 이동할 수 없을 때
if (room[nr][nc] != 0) return null;
else return new int[]{nr, nc, nd};
}
private static int[] moveBack(int r, int c, int d) {
int nd = d == 0 ? 2 : d == 1 ? 3 : d == 2 ? 0 : 1;
int nr = r + dr[nd];
int nc = c + dc[nd];
// 더이상 물러날 곳이 없을때
if (room[nr][nc] == 1) return null;
else return new int[]{nr, nc, d};
}
private static boolean findDirty(int r, int c) {
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (room[nr][nc] == 0) return true;
}
return false;
}
}
결과
리뷰
- 문제에 주어진 로직을 그대로 구현하는 문제여서 난이도는 높지 않았습니다.
- 로직을 메서드 단위로 분리해서 구현하니 좀더 직관적으로 구현이 가능했습니다.
- BFS를 구현하기 위해 불필요한 Queue 객체를 추가로 생성한 것 같아 아쉽습니다.
- BFS나 DFS를 사용하기에 앞서 탐색 시 기존 경로를 저장할 필요가 있는지를 따져보고 도입하는게 좋을 것 같습니다.
References
URL | 게시일자 | 방문일자 | 작성자 |
---|
유효하지 않은 배열 인덱스에 접근할때 발생하는 오류입니다. ↩︎