[BOJ 1175] 배달 (Java)

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

1175번: 배달

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

public class Main_BOJ_1175_1 {
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N, M;
	static int[][] map;
	static boolean[][][][] check;
	static int start_r, start_c;
	static int answer=-1;
	static ArrayList<int[]> dest=new ArrayList<>();
	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());
		map=new int[N][M];
		check=new boolean[N][M][4][4];
		for (int i=0; i<N; i++) {
			String s=br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j]=s.charAt(j);
				if (map[i][j]=='C') {
					dest.add(new int[] {i,j});
				}
				else if (map[i][j]=='S') {
					start_r=i;
					start_c=j;
				}
			}
		}
		bfs();
		System.out.println(answer);
	}
	private static void bfs() {
		Queue<int[]> q=new LinkedList<>();
		q.add(new int[] {start_r, start_c, -1, 0, 0});
		while (!q.isEmpty()) {
			int[] curr=q.poll();
			int r=curr[0];
			int c=curr[1];
			int d=curr[2];
			int state=curr[3];
			int cnt=curr[4];
			if (state==3) {
				answer=cnt;
				break;
			}
			for (int i=0; i<4; i++) {	
				if (i==d) continue;
				int nr=r+dr[i];
				int nc=c+dc[i];
				if (nr<0 || nc<0 || nr>=N || nc>=M) continue;
				if ((map[nr][nc]=='.' || map[nr][nc]=='S') && !check[nr][nc][state][i]) {
					check[nr][nc][state][i]=true;
					q.add(new int[] {nr, nc, i, state, cnt+1});
				}
				if (map[nr][nc]=='C') {
					int num=isDest(nr, nc);
					int nstate=state|(1<<num);
					if (!check[nr][nc][nstate][i]) {
						check[nr][nc][nstate][i]=true;
						q.add(new int[] {nr, nc, i, nstate, cnt+1});
					}
				}
			}
		}
		
	}
	
	private static int isDest(int r, int c) {
		for (int i=0; i<2; i++) {
			if (r==dest.get(i)[0] && c==dest.get(i)[1]) return i;
		}
		return -1;
	}

}

4차원 visited 배열을 이용하는 문제.

 

4차원 배열에서 1번, 2번 목적지를 방문했냐와 어떤 방향으로 (i,j) 번에 도착했는지 체크하는 것을 추가로 두었다. 

처음에 어떤 방향으로 (i,j) 번에 도착했는지 표시하지 않아서 오답이었다. 이 문제같은 경우에는 같은 곳을 여러번(그러나 다른 방향으로) 방문할 수 있음에 유의하자. 

각 목적지 방문은 비트 연산을 이용해 state 상태를 나타내주었다.