[백준] 17244.아맞다우산 (java) / BFS, Permutation

@시뮬레이션

풀면서 permu + bfs, 완탐 이렇게 돌리면 터지지 않을까 고민하면서 풀었는데

돌려보니 의외로 빨라서 당황.

시간복잡도 계산하는 연습이 조금 더 필요할 듯 하다.

 

문제 자체는 크게 어렵지 않았는데, 챙겨야 하는 물건이 없을 수 있다는 점을 간과해서 런타임 에러가 떴고, 그걸 잡느라 조금 고생했다.

근데 또 물건이 없을 때에도 시작점과 도착점 사이에 벽이 있을 수 있다는 사실을 간과해서, 또 약간의 삽질을..

문제 조건을 꼼꼼히 보는 습관을 들여야겠다.

 

Gold 2라고 되어있어서 쫄았는데, 그정도 문제는 아닌 것 같고

bfs 연습하기 좋은 코드인 듯!

 

 

#

구현 방법

1. 맵을 입력받으면서 물건의 위치를 ArrayList에 저장한다

2. 물건 개수 크기의 배열을 만들어서 nextPermutation을 돌린다

3. 넥퍼로 구한 순열마다 bfs를 돌려서 최단경로를 구한다

4. 3에서 구한 최단경로중 가장 짧은 거리를 출력한다

 

 

package bj_17244_아맞다우산;

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

public class Main {

	private static int n, m, sx, sy, ex, ey, minSum = Integer.MAX_VALUE, num, number[];
	private static int[] dx = {0, -1, 0, 1}, dy = {-1, 0, 1, 0};
	private static char[][] map;
	private static boolean[][] visit;
	private static Queue<int[]> q = new LinkedList<>();
	private static ArrayList<int[]> list = new ArrayList<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		map = new char[n][m];

		//맵 입력 
		for (int i = 0; i < n; i++) {
			map[i] = br.readLine().toCharArray();
			
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 'S') {
					sx = i; sy = j;
				} else if (map[i][j] == 'E') {
					ex = i; ey = j;
				} else if (map[i][j] == 'X') {
					list.add(new int[]{i, j});
				}
			}
		}
		
		//permutation을 위한 배열 생성 
		num = list.size();
		number = new int[num];
		for (int i = 0; i < num; i++)
			number[i] = i;
		
		//물건이 하나도 없을 경우 
		if (num == 0) {
			q.add(new int[] {sx, sy, 0});
			visit = new boolean[n][m];
			visit[q.peek()[0]][q.peek()[1]] = true;
			System.out.println(bfs(ex, ey));
			System.exit(0);
		}
		
		do {
			int tempSum = 0;
			for (int i = 0; i <= num; i++) {

				q.clear();
				if (i == 0)		//시작점을 위한 
					q.add(new int[] {sx, sy, 0});
				else
					q.add(new int[] {list.get(number[i - 1])[0], list.get(number[i - 1])[1], 0});

				visit = new boolean[n][m];
				visit[q.peek()[0]][q.peek()[1]] = true;
				
				if (i < num)
					tempSum += bfs(list.get(number[i])[0], list.get(number[i])[1]);
				else			//끝점을 위한 
					tempSum += bfs(ex, ey);
				
				if (tempSum > minSum) break;	//가지치기
			}
			minSum = minSum > tempSum ? tempSum : minSum;
		} while (nextPermutaion());
		
		System.out.println(minSum);
	}

	private static int bfs(int endX, int endY) {
		while (!q.isEmpty()) {
			int[] temp = q.poll();
			
			for (int d = 0; d < 4; d++) {
				int nx = temp[0] + dx[d];
				int ny = temp[1] + dy[d];
				
				if (nx < 0 || nx >= n || ny < 0 || ny >= m || visit[nx][ny] || map[nx][ny] == '#') continue;
				
				if (nx == endX && ny == endY) return temp[2] + 1;
				
				visit[nx][ny] = true;
				q.add(new int[]{nx, ny, temp[2] + 1});
			}
		}
		return 0;
	}

	private static boolean nextPermutaion() {
		int i = num - 1;
		while (i > 0 && number[i - 1] >= number[i]) --i;
		if (i == 0) return false;
		
		int j = num - 1;
		while (number[i - 1] >= number[j]) --j;
		
		swap(i - 1, j);
		
		j = num - 1;
		while (i < j) swap(i++, j--);
		
		return true;
	}

	private static void swap(int i, int j) {
		int temp = number[i];
		number[i] = number[j];
		number[j] = temp;
	}
}

 

 

#

삽질 포인트

1. 물건이 없을 수 있다는 점 간과

2. 물건이 없어도 시작점과 도착점 사이에 벽이 있을 수 있다는 점

 

끝!