BOJ 13901 로봇(Java)

문제 탐색하기

• 로봇은 사용자가 지정한 방향을 일직선으로 움직인다.
• 이동 중 벽이나 방문한 지역, 장애물을 만날 경우 로봇은 사용자가 지정한 다음 방향으로 움직인다.
• 사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가서 위의 과정을 반복한다.
• 로봇이 움직일 수 없을 경우 동작을 멈춘다.

코드 설계하기

구현 방법

1. 필요한 정보 입력받고 초기화
   • map[][]: 장애물 위치 저장용 (-1로 표시)
   • visited[][]: 로봇이 방문한 위치 체크
   • dx[], dy[]: 상하좌우 방향 벡터
   • dir[]: 사용자 지정 방향 순서를 0~3으로 저장
2. BFS 수행
   • 현재 위치에서 4방향 순회
     • 현재 dirIdx 기준으로 탐색
     • 갈 수 있는 방향 발견 시 해당 방향으로 이동
     • 이동했으면 큐에 추가, visited 체크
     • 이동 후 dirIdx 업데이트
     • 다시 반복
   • 더 이상 이동할 수 없을 때 종료
3. 출력
   • 마지막으로 이동한 위치 (r, c) 출력

시간 복잡도

• 최대 방 크기: R x C ≤ 1000 x 1000 = 10^6
• 각 칸은 최대 한 번만 방문하므로:
  • 최악의 경우 시간 복잡도는 O(R × C)
• 장애물 입력: O(K)
• 전체 시간 복잡도:
  O(R × C + K)

정답 코드 (Java)

import java.io.*;  
import java.util.LinkedList;  
import java.util.Queue;  
import java.util.StringTokenizer;  
  
public class b13901 {  
    private static int R, C, K, dirIdx, r, c;  
    private static int[][] map;  
    private static boolean[][] visited;  
    private static int[] dir = new int[4];  
    private static int[] dx = {-1, 1, 0, 0};  
    private static int[] dy = {0, 0, -1, 1};  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        R = Integer.parseInt(st.nextToken());  
        C = Integer.parseInt(st.nextToken());  
        st = new StringTokenizer(br.readLine());  
        K = Integer.parseInt(st.nextToken());  
        map = new int[R][C];  
        visited = new boolean[R][C];  
  
        // 장애물  
        for (int i = 0; i < K ; i++){  
            st = new StringTokenizer(br.readLine());  
            int x = Integer.parseInt(st.nextToken());  
            int y = Integer.parseInt(st.nextToken());  
            map[x][y] = -1;  
        }  
  
        st = new StringTokenizer(br.readLine());  
        int sr = Integer.parseInt(st.nextToken());  
        int sc = Integer.parseInt(st.nextToken());  
  
        st = new StringTokenizer(br.readLine());  
        for (int i = 0; i < 4 ; i++) {  
            dir[i] = Integer.parseInt(st.nextToken()) - 1;  
        }  
  
        solve(sr, sc);  
        bw.write(r + " " + c + "\n");  
        bw.flush();  
        br.close();  
        bw.close();  
    }  
  
    private static void solve(int sr, int sc) {  
        Queue<int[]> q = new LinkedList<>();  
        visited[sr][sc] = true;  
        q.add(new int[]{sr, sc});  
  
        while (!q.isEmpty()) {  
            int[] cur = q.poll();  
            for (int i = 0; i < 4; i++) {  
                int d = dir[(dirIdx + i) % 4];  
                int x = cur[0] + dx[d];  
                int y = cur[1] + dy[d];  
  
                if ( 0 > x || 0 > y || x >= R || y >= C || visited[x][y] || map[x][y] == -1) continue;  
  
                visited[x][y] = true;  
                q.add(new int[]{x, y});  
                dirIdx = (dirIdx + i) % 4;  
                r = x;  
                c = y;  
                break;  
            }  
        }  
    }  
}