백준 1400번: 화물차

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

 

현재 위치에서 도로로 이동해서 목표 위치로 이동할 때 걸리는 시간을 구하는 문제이다. 갈 수 있는 길 중 교차로가 있으며 교차로는 신호등이 있어 각각 초기 방향, 수평 주기, 수직 주기가 있어 각 주기에 맞추어 해당 방향으로 진입할 수 있다. 교차로에 진입 후에는 원하는 방향으로 이동할 수 있다. 도착 가능하면 최소 시간을, 불가능하면 impossible을 출력한다.

 

인도는 '.', 이동 가능한 일반 도로는 '#', 교차로는 최대 10개이며 0~9으로 표현된다. 도로의 정보, 교차로의 신호 정보를 저장하기 위해 커스텀 클래스 및 배열을 이용하였다.

static class Intersection {
    
    char init;
    int h, v;
    
    Intersection(char init, int h, int v) {
        this.init = init;
        this.h = h;
        this.v = v;
    }
}

int startR = 0, startC = 0;
int maxId = -1;
map = new char[N][M];
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] == 'A') {
            startR = i;
            startC = j;
        } else if (map[i][j] >= '0' && map[i][j] <= '9') {
            maxId = Math.max(maxId, map[i][j] - '0');
        }
    }
}

intersections = new Intersection[maxId + 1];
for (int i = 0; i <= maxId; i++) {
    st = new StringTokenizer(br.readLine());
    int id = Integer.parseInt(st.nextToken());
    char dir = st.nextToken().charAt(0);
    int h = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    intersections[id] = new Intersection(dir, h, v);
}

 

 

교차로가 아닌 도로는 그냥 이동하고 교차로는 현재 시간에서 진입 가능한 시간까지 기다린 후 이동하여 최소시간을 시간 기준으로 우선순위 큐에 넣어서 방문한다.

static class Node implements Comparable<Node> {
    
    int r, c, t;
    
    Node(int r, int c, int t) {
        this.r = r;
        this.c = c;
        this.t = t;
    }
    
    @Override
    public int compareTo(Node o) {
        return this.t - o.t;
    }
}

static String solve(int sr, int sc) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    int[][] dist = new int[N][M];
    for (int i = 0; i < N; i++) {
        Arrays.fill(dist[i], Integer.MAX_VALUE);
    }
    
    dist[sr][sc] = 0;
    pq.add(new Node(sr, sc, 0));
    
    while (!pq.isEmpty()) {
        Node curr = pq.poll();
        
        if (curr.t > dist[curr.r][curr.c]) {
            continue;
        }
        if (map[curr.r][curr.c] == 'B') {
            return String.valueOf(curr.t);
        }
        
        for (int i = 0; i < 4; i++) {
            int nr = curr.r + dr[i];
            int nc = curr.c + dc[i];
            
            if (nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc] == '.') {
                continue;
            }
            
            int waitT = curr.t;
            if (map[nr][nc] >= '0' && map[nr][nc] <= '9') {
                Intersection inter = intersections[map[nr][nc] - '0'];
                boolean isMoveVertical = (i < 2);
                
                while (true) {
                    int cycle = inter.h + inter.v;
                    int rem = (waitT) % cycle;
                    boolean isGreenHorizontal;
                    
                    if (inter.init == '-') {
                        isGreenHorizontal = (rem < inter.h);
                    } else {
                        isGreenHorizontal = !(rem < inter.v);
                    }
                    
                    if ((isMoveVertical && !isGreenHorizontal) || (!isMoveVertical && isGreenHorizontal)) {
                        break;
                    }
                    waitT++;
                }
            }
            
            int nextT = waitT + 1;
            
            if (dist[nr][nc] > nextT) {
                dist[nr][nc] = nextT;
                pq.add(new Node(nr, nc, nextT));
            }
        }
    }
    return "impossible";
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 화물차1400 {
    
    static int N, M;
    static char[][] map;
    static Intersection[] intersections;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            String line = br.readLine();
            if (line == null || line.trim().isEmpty()) {
                break;
            }
            StringTokenizer st = new StringTokenizer(line);
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            if (N == 0 && M == 0) {
                break;
            }
            
            int startR = 0, startC = 0;
            int maxId = -1;
            map = new char[N][M];
            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] == 'A') {
                        startR = i;
                        startC = j;
                    } else if (map[i][j] >= '0' && map[i][j] <= '9') {
                        maxId = Math.max(maxId, map[i][j] - '0');
                    }
                }
            }
            
            intersections = new Intersection[maxId + 1];
            for (int i = 0; i <= maxId; i++) {
                st = new StringTokenizer(br.readLine());
                int id = Integer.parseInt(st.nextToken());
                char dir = st.nextToken().charAt(0);
                int h = Integer.parseInt(st.nextToken());
                int v = Integer.parseInt(st.nextToken());
                intersections[id] = new Intersection(dir, h, v);
            }
            
            System.out.print(solve(startR, startC));
            br.readLine();
        }
    }
    
    static String solve(int sr, int sc) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[][] dist = new int[N][M];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        
        dist[sr][sc] = 0;
        pq.add(new Node(sr, sc, 0));
        
        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            
            if (curr.t > dist[curr.r][curr.c]) {
                continue;
            }
            if (map[curr.r][curr.c] == 'B') {
                return String.valueOf(curr.t);
            }
            
            for (int i = 0; i < 4; i++) {
                int nr = curr.r + dr[i];
                int nc = curr.c + dc[i];
                
                if (nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc] == '.') {
                    continue;
                }
                
                int waitT = curr.t;
                if (map[nr][nc] >= '0' && map[nr][nc] <= '9') {
                    Intersection inter = intersections[map[nr][nc] - '0'];
                    boolean isMoveVertical = (i < 2);
                    
                    while (true) {
                        int cycle = inter.h + inter.v;
                        int rem = (waitT) % cycle;
                        boolean isGreenHorizontal;
                        
                        if (inter.init == '-') {
                            isGreenHorizontal = (rem < inter.h);
                        } else {
                            isGreenHorizontal = !(rem < inter.v);
                        }
                        
                        if ((isMoveVertical && !isGreenHorizontal) || (!isMoveVertical && isGreenHorizontal)) {
                            break;
                        }
                        waitT++;
                    }
                }
                
                int nextT = waitT + 1;
                
                if (dist[nr][nc] > nextT) {
                    dist[nr][nc] = nextT;
                    pq.add(new Node(nr, nc, nextT));
                }
            }
        }
        return "impossible";
    }
    
    static class Intersection {
        
        char init;
        int h, v;
        
        Intersection(char init, int h, int v) {
            this.init = init;
            this.h = h;
            this.v = v;
        }
    }
    
    static class Node implements Comparable<Node> {
        
        int r, c, t;
        
        Node(int r, int c, int t) {
            this.r = r;
            this.c = c;
            this.t = t;
        }
        
        @Override
        public int compareTo(Node o) {
            return this.t - o.t;
        }
    }
}