글 읽기 - 탈옥 문제 문의합니다 (가지치기)

sunminjeon 3년 전 0

탈옥 문제 문의드립니다.

바깥과 감옥이 연결된 문('#')을 탐색하기 위해서, 감옥 사방을 빈 공간 ('.')으로 만들어주고

감옥 바깥을 돌아다닐 수 있는 상근이와 죄수2명, 총 3번의 다익스트라를 돌리는데요,

감옥 바깥은 상근이만 접근 가능하고, 나머지 죄수 2명은 접근 불가하지 않나요?

어차피 답은 감옥 안의 dist로만 보니까요.

가지치기를 하려고 아래 코드를 추가하였는데, 추가했을 경우 왜 답이 틀리게 되는지 궁금합니다.

어떤 예외케이스가 있을 수 있을까요?

// 상근이를 제외한 죄수들이 감옥 밖을 갈 경우 continue

// if(index != 0 && (x == 0 || x == N+1 || y == 0 || y == M+1)) continue;

import java.io.*;
import java.util.*;

public class Main {
	
	static char[][] list = new char[102][102];
	
	static List<Node> start;
	
    static int N, M;
     
    static int result;
    
    static int INF = 10000;
    
    static int[][] offset = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    static class Node implements Comparable<Node>{
    	int x;
    	int y;
    	int dist;
    	public Node() {}
    	public Node(int x, int y, int dist) {
    		this.x = x;
    		this.y = y;
    		this.dist = dist;
    	}
		@Override
		public int compareTo(Node o) {
			return this.dist - o.dist;
		}
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
         
        int t,x,y,i,j = 0;
         
        for (t = 1; t <= T; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            
            result = 0;
            start = new ArrayList<Node>();
            start.add(new Node(0, 0, 0));
            
            // 가장자리를  +1 씩 더하여, 빈 공간으로 둘러싸게 만든다.
            for (x = 0; x <= N+1; x++) {
            	if(x == 0 || x == N+1) {
            		for (y = 0; y <= M+1; y++) {
            			list[x][y] = '.';
            		}
            	}
            	else {
            		st = new StringTokenizer(br.readLine());
                	String str = st.nextToken();
                	for (y = 0; y <= M+1; y++) {
                		if(y == 0 || y == M+1) {
                			list[x][y] = '.';
                			continue;
                		}
                		list[x][y] = str.charAt(y-1);
                		if(list[x][y] == '$') {
                			start.add(new Node(x,y,0));
                		}
                	}
            	}
            }
            
            int[][] dist1 = dijkstra(start.get(0), 0);
            int[][] dist2 = dijkstra(start.get(1), 1);
            int[][] dist3 = dijkstra(start.get(2), 2);
            
            int min = INF;
            for (x = 1; x <= N; x++) {
            	 for (y = 1; y <= M; y++) {
            		 if(list[x][y] == '*') continue;
            		 
            		 int count = dist1[x][y] + dist2[x][y] + dist3[x][y];
            		 if(list[x][y] == '#') count -= 2;
            		 min = Math.min(min, count);
                 }
            }
           
            result = min;
            bw.append(result + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    
    public static int[][] dijkstra(Node node, int index) {
    	int[][] dist = new int[N+2][M+2];
    	for (int x = 0; x <= N+1; x++) {
     		for (int y = 0; y <= M+1; y++) {
     			dist[x][y] = INF;
     		}
     	}
    	
    	PriorityQueue<Node> pq = new PriorityQueue<Node>();
    	pq.add(node);
    	dist[node.x][node.y] = 0;
    	
    	while(!pq.isEmpty()) {
    		Node startNode = pq.poll();
    		int d = startNode.dist;
    		int sx = startNode.x;
    		int sy = startNode.y;
            
    		for(int i = 0; i < 4; i++) {
    			int x = sx + offset[i][0];
    			int y = sy + offset[i][1];
    			int dt = d;
    			
    			// 벽이거나 범위를 벗어난 공간이라면 continue
    			if(x > N+1 || x < 0 || y > M+1 || y < 0 || list[x][y] == '*') continue;
    			
    			// 죄수들이 감옥 밖을 갈 경우 continue
    			// if(index != 0 && (x == 0 || x == N+1 || y == 0 || y == M+1)) continue;
    			
    			// 문이면 거리 증가
    			if(list[x][y] == '#') dt ++;
    			
    			if(dist[x][y] == INF || dist[x][y] > dt) {
                    dist[x][y] = dt;
    				pq.add(new Node(x, y, dt));
    			}
    		}
    	}
    	return dist;
    }
}

playsworld16 3년 전 4

한 죄수가 감옥 내의 어떤 곳에 도달하는 것에 있어서

감옥 내로만 이동하는 경우보다

문을 열고 감옥 밖으로 가서 다시 들어오는 경우가 더 적은 비용이 들 경우 문제가 생깁니다.

단순히 말해서 다음과 같은 경우에 답을 제대로 내지 못합니다.

/*
1
3 5
*****
#$∗$#
*****

답: 2
*/

sunminjeon 3년 전 0

이해했습니다, 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

탈옥 문제 문의합니다 (가지치기)

sunminjeon 3년 전 0

playsworld16 3년 전 4

sunminjeon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말