[JAVA] # 14503 로봇청소기

[JAVA] # 14503 로봇청소기

https://www.acmicpc.net/problem/14503

package CodingTestMemory.BJ.Simulation.P14503; import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class P14503 { public static class Node { int x, y, dir; public Node(int x, int y, int dir) { this.x = x; this.y = y; this.dir = dir; } } static int N, M; static int cnt; static int[][] map; static boolean[][] visited; public static void func(int st_x, int st_y, int st_dir) { Queue queue = new LinkedList<>(); queue.add(new Node(st_x, st_y, st_dir)); while(!queue.isEmpty()) { Node e = queue.poll(); if(!visited[e.y][e.x]) { // 아직 청소를 하지 않은 점이라면 visited[e.y][e.x] = true; // 1. 현재 위치를 청소한다 cnt++; } int flag = 0; // 네 방향 중에 청소할 부분이 있는지 유무 체크용 int dir = e.dir; // 현재 바라보고 있는 방향 for(int i = 0; i < 4; i++) { // 4방향을 모두 돌아본다 int nx = e.x, ny = e.y; dir = (dir + 3) % 4; // 현재 바라보는 방향에서 왼쪽방향부터 탐색 (북->서->남->동) switch (dir) { // 방향 잡기 case 0: // 북 ny -= 1; break; case 1: // 동 nx += 1; break; case 2: // 남 ny += 1; break; default: // 서 nx -= 1; break; } if(map[ny][nx] == 1 || visited[ny][nx]) { // 벽이거나, 이미 청소를 했다면 continue; } queue.add(new Node(nx, ny, dir)); flag = 1; // 청소할 곳이 있다 break; } if(flag == 0) { // 4방향 모두 청소할 곳이 없으면 int nx = e.x, ny = e.y; switch (e.dir) { // 방향을 유지한 채로 한칸 후진 case 0: // 북(-> 남) ny += 1; break; case 1: // 동(-> 서) nx -= 1; break; case 2: // 남 ny -= 1; break; default: // 서 nx += 1; break; } if(map[ny][nx] == 1) { // 후진할 곳이 벽이면 return; } queue.add(new Node(nx, ny, e.dir)); } } } 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 stk = new StringTokenizer(br.readLine()); N = Integer.parseInt(stk.nextToken()); M = Integer.parseInt(stk.nextToken()); map = new int[N][M]; visited = new boolean[N][M]; stk = new StringTokenizer(br.readLine()); // 로봇청소기 출발 위치정보 int start_y = Integer.parseInt(stk.nextToken()); int start_x = Integer.parseInt(stk.nextToken()); int start_dir = Integer.parseInt(stk.nextToken()); for(int j = 0; j < N; j++) { // 지도 정보 stk = new StringTokenizer(br.readLine()); for(int i = 0; i < M; i++) { map[j][i] = Integer.parseInt(stk.nextToken()); } } func(start_x, start_y, start_dir); bw.write(cnt + "

"); bw.flush(); bw.close(); } }

시키는 대로만 고분고분 따라하면 여차저차 풀리기는 하는 문제였다.

앞으로 똑바로 갈것이지 괜히 왼쪽으로 돌고 후진하고 난리를 치는 청소기 때문에 골치를 좀 먹었지만

그렇게 까다로운 문제는 아니었다.

방향을 잡고 왼쪽으로 회전하는것만 신경써주면 되는데

0 - 북

1 - 동

2 - 남

3 - 서

굳이 또 오른쪽으로 회전해주시는 출제자님 덕분에 다른 방식으로 방향을 잡아줘야 한다

(현재 방향 + 3) % 4 를 해주면 현재 바라보고 있는 방향에서 왼쪽을 바라볼 수 있게 값을 내준다.

다만 저 중복되는 switch 부분을 조금 깔끔하게 정리할 수 있을 것 같은데 싶은 아쉬움이 살짝 있는데,

또 굳이 큐가 없어도 될 것같긴 한데,, BFS 문제를 풀어보다 보니 자연스레 BFS꼴이 갖춰져버렸다

귀찮아서 못고치겠다. :D

from http://sedangdang.tistory.com/115 by ccl(A) rewrite - 2021-09-12 22:26:57