[JAVA] 백준 1175번: 배달

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

1175번: 배달

✅ 골드 Ⅰ

 

🔶 풀이

배달해야하는 곳은 총 2곳이고, 같은 방향으로 연속해서 이동할 수 없음.

단순 bfs를 돌리면서 신경써야할 건 총 두 가지였다.

 

1️⃣ 같은 방향으로 연속해서 이동할 수 없다.

2️⃣ 현재까지 배달한 곳

 

1️⃣번의 경우에는 아래와 같은 방법으로 쉽게 해결할 수 있다. 

 // 같은 방향으로 연속해서 움직일 수 없음
if (cur.d == d) continue;

 

2️⃣번의 경우에 필자는 배달해야하는 곳에 임의로 값을 줘서 Queue를 돌릴 때 값을 넣어줬다.

if (cur.x == end[0].x && cur.y == end[0].y && cur.v != 1) cur.v += 1;
if (cur.x == end[1].x && cur.y == end[1].y && cur.v != 2) cur.v += 2;
if (cur.v == 3) return cur.t;

첫 번째로 입력된 배달 지점을 1 / 두 번째로 입력된 배달 지점을 2로 설정해두고 위와 같은 방법으로 구분했다. 둘 다 배달이 완료된 경우에는 값이 3이 될테니까 그 시점에 반복문을 종료하면 된다.

 

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static char[][] map;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static Node[] end;
	
    public static class Node {
        int x, y, d, t, v;
		
        public Node (int x, int y, int d, int t, int v) {
            this.x = x; // 좌표 x
            this.y = y; // 좌표 y
            this.d = d; // 방향
            this.t = t; // 소요 시간
            this.v = v; // 배달이 완료된 곳을 알기 위한 값
        }
    }
	
    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 char[N][M];
		
        int sX = 0;
        int sY = 0;
        end = new Node[2];
        int idx = 0;
		
        for (int i=0; i<N; i++) {
            String tmp = br.readLine();
            for (int j=0; j<M; j++) {
                map[i][j] = tmp.charAt(j);
				
                if (map[i][j] == 'S') {
                    sX = i;
                    sY = j;
                }
				
                if (map[i][j] == 'C') {
                    end[idx++] = new Node(i, j, -1, 0, 0);
                }
            }
        }
		
        int ans = bfs(sX, sY);
        System.out.println(ans);
    }
	
    public static int bfs (int x, int y) {
        Queue<Node> q = new LinkedList<>();
        boolean[][][][] visited = new boolean[N][M][4][3]; // x, y, 방향, 방문여부
		
        visited[x][y][0][0] = true;
        visited[x][y][1][0] = true;
        visited[x][y][2][0] = true;
        visited[x][y][3][0] = true;
        q.add(new Node(x, y, -1, 0, 0));
		
        while (!q.isEmpty()) {
            Node cur = q.poll();
			
            // 현재까지 배달 완료한 곳을 1, 2로 설정
            if (cur.x == end[0].x && cur.y == end[0].y && cur.v != 1) cur.v += 1;
            if (cur.x == end[1].x && cur.y == end[1].y && cur.v != 2) cur.v += 2;
            if (cur.v == 3) return cur.t;
			
            for (int d=0; d<4; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];
				
                // 같은 방향으로 연속해서 움직일 수 없음
                if (cur.d == d) continue;
                if (nx < 0 || ny < 0 || nx > N-1 || ny > M-1 || map[nx][ny] == '#' || visited[nx][ny][d][cur.v]) continue;
				
                q.add(new Node(nx, ny, d, cur.t+1, cur.v));
                visited[nx][ny][d][cur.v] = true;
            }
        }
		
        return -1;
    }
}