출처 https://www.acmicpc.net/problem/14503 접근 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; } } 결과 ...