[Java] 백준 1726번 : 로봇

1. 문제

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

1726번: 로봇

 

 

 

2. 풀이과정

문제를 처음 봤을 때, BFS를 떠올렸다가 1~3칸 전진과 1(90도)~2(180도)번 전진 처리가 복잡해 DFS로 풀었다.

그런데, 풀고나서 보니 DFS보다 BFS를 썼을 때 더 빠르게 구현할 수 있을 것 같아 BFS로 다시 풀어보았다.

 

결과적으로 BFS가 메모리, 시간 측면에서 더 효율적이다.

 

아래 그림은 두 코드에서 사용한 방향 전환할 때, 걸리는 시간을 구하는 방법이다.

동서남북 => 시계방향 기준으로 값을 변환한 후, 빼기를 통해 회전수를 구했다.

 

 

 

[방법1] DFS

* 전체 경로를 탐색하기 때문에 가지치기가 중요하다.

 

가지치기 방법

= 이동하면서 (해당 칸에 저장된 거리 값) < (현재 값)이면, 계속 진행! 아니면 더 갈 필요 없으니 return 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int goal[];
	static int map[][];
	static int dx[], dy[];
	
    //회전 횟수 반환
	public static int getTurn(int from, int to) {
		int dxy[] = {1, 3, 2, 4};//동서남북 => 시계방향과 매칭
		int dir = Math.abs(dxy[from]-dxy[to]);
		if(dir==3) dir=1;
		return dir;
	}

	public static void dfs(int x, int y, int d, int distance, int jump) {
		
		if(x == goal[0] && y == goal[1]) {
			map[x][y] = Math.max(map[x][y], distance-getTurn(d-1, goal[2]-1));
			return;
		}
		
		if(map[x][y] < distance) {
			map[x][y] = distance;
		}
		else
			return;
		
		for(int j=0; j<4; j++) {//4방향
        	//현재 방향이랑 같으면(=전진하겠다) 
            //&& 앞 단계에 1칸 혹은 2칸 전진했을 경우는 pass (또 직진할 경우 3칸 전진한게 더 빠르기때문)
			if(d==j+1 && jump!=3) {
					continue;
			}
			else {
				//방향 전환
				int dir = getTurn(d-1, j);
				//1칸, 2칸, 3칸 전진
				for(int k=1;k<=3;k++) {
					int nx = x+k*dx[j];
					int ny = y+k*dy[j];
					if(map[nx][ny]==1) break;
					dfs(nx, ny, j+1, map[x][y]-dir-1, k);
				}
			}	
		}
		
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//동서남북 = 오왼밑위
		dx = new int[] {0, 0, 1, -1}; 
		dy = new int[] {1, -1, 0, 0};
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N+2][M+2];
		for(int i=1;i<=N;i++) {
			map[i][0] = 1;
			map[i][M+1] = 1;
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=M;j++) {
				if(st.nextToken().charAt(0)=='1')
					map[i][j] = 1;
				else
					map[i][j] = Integer.MIN_VALUE;
			}
		}
		//벽세우기
		//가로
		for(int i=0; i<M+2; i++) {
			map[0][i] = 1;
			map[N+1][i] = 1;
		}
		
		//현재 로봇의 위치와 방향
		st = new StringTokenizer(br.readLine());
		int robot[] = new int[3];
		robot[0] = Integer.parseInt(st.nextToken());
		robot[1] = Integer.parseInt(st.nextToken());
		robot[2] = Integer.parseInt(st.nextToken());
		//도착지점 로봇의 위치와 방향
		goal = new int[3];
		st = new StringTokenizer(br.readLine());
		goal[0] = Integer.parseInt(st.nextToken());
		goal[1] = Integer.parseInt(st.nextToken());
		goal[2] = Integer.parseInt(st.nextToken());
		
		dfs(robot[0], robot[1], robot[2], 0, 3);//이동 거리, 한번에 직진한 거리
		
		System.out.println(-map[goal[0]][goal[1]]);
	}
}

 

[결과]

 

---

​

[방법2] BFS (효율적)

 

Queue에서 뽑은 해당 node에서 할 수 있는 일

 

1. 전진

1) 1칸 전진2) 2칸 전진3) 3칸 전진=> for문 돌리자

 

2. 회전

1) 동

2) 서

3) 남

4) 북

=> for문 돌리자

 

방향마다 방문체크 해야하기 때문에 visited를 3차원 배열로 사용했다. 해당 노드에서의 방향에 따라 회전수(최종거리)가 바뀌기 때문에, 한 방향에서 방문했더라도 다른 방향으로 왔을 때 또 고려해주어야 함.

 

짧게 말해서는 해당 노드에서 어떤 방향이냐에 따라 미래가 바뀐다고 보면 된다. 같은 방향이 또 올 경우 미래가 같으니 또 check해 줄 필요가 없는 것이다.

*미래 = 앞으로 회전을 하던 직진을 하던 등 갈 모든 경로

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Boj1726_Robot4 {

	static int N, M;
	static int goal[];
	static char map[][];
	static int dx[], dy[];
	
	public static int getTurn(int from, int to) {
		int dxy[] = {0, 1, 3, 2, 4};//동서남북 => 시계방향과 매칭
		int dir = Math.abs(dxy[from]-dxy[to]);
		if(dir==3) dir=1;
		return dir;
	}

	public static int bfs(int x, int y, int d) {
		int result = Integer.MAX_VALUE;
		boolean visited[][][] = new boolean[N+2][M+2][4];//동서남북
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {x, y, d, 0});//x좌표, y좌표, 방향, 거리
		
		while(!q.isEmpty()) {
			int[] node = q.poll();
			
			//도착지 오면
			if(node[0]==goal[0] && node[1]==goal[1] && node[2]==goal[2]) {
				result = node[3] + getTurn(node[2], goal[2]);
				break;
			}
			
			//1칸, 2칸, 3칸 전진
			for(int i=1;i<=3;i++) {
				int nx = node[0]+i*dx[node[2]];
				int ny = node[1]+i*dy[node[2]];
				
				if(map[nx][ny]=='1') break;//벽있으면 전진 멈춤
				
				if(!visited[nx][ny][node[2]-1]) {
					visited[nx][ny][node[2]-1] = true;
					q.offer(new int[] {nx, ny, node[2], node[3]+1});
				}
			}
			
			//4방향 탐색
			for(int i=1; i<=4; i++) {
				//방향 전환값
				int dir = getTurn(node[2], i);
				if(!visited[node[0]][node[1]][i-1]) {
					visited[node[0]][node[1]][i-1] = true;
					q.offer(new int[] {node[0], node[1], i, node[3]+dir});
				}
			}
		}
		return result;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//동서남북 = 오왼밑위
		dx = new int[] {0, 0, 0, 1, -1}; //맨 앞 칸 버림
		dy = new int[] {0, 1, -1, 0, 0};
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N+2][M+2];
		for(int i=1;i<=N;i++) {
			map[i][0] = '1';
			map[i][M+1] = '1';
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=M;j++) {
				map[i][j] = st.nextToken().charAt(0);
			}
		}
		//벽세우기
		//가로
		for(int i=0; i<M+2; i++) {
			map[0][i] = '1';
			map[N+1][i] = '1';
		}
		
		//현재 로봇의 위치와 방향
		st = new StringTokenizer(br.readLine());
		int robot[] = new int[3];
		robot[0] = Integer.parseInt(st.nextToken());
		robot[1] = Integer.parseInt(st.nextToken());
		robot[2] = Integer.parseInt(st.nextToken());
		//도착지점 로봇의 위치와 방향
		goal = new int[3];
		st = new StringTokenizer(br.readLine());
		goal[0] = Integer.parseInt(st.nextToken());
		goal[1] = Integer.parseInt(st.nextToken());
		goal[2] = Integer.parseInt(st.nextToken());
		
		System.out.println(bfs(robot[0], robot[1], robot[2]));
	}
}

 

[결과]