백준 17244번 : 아맞다우산 (Java)

 문제

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

17244번: 아맞다우산

17244 아맞다우산

 

 구현 방법

비트마스킹을 사용하여 시간을 좀 더 줄일 수 있었겠지만 따로 비트마스킹을 사용하진 않았습니다.

 

저는 각 물건에서 현재 위치, 나가는 위치, 다른 물건 위치 까지의 거리를 모두 구해준 후

순열로 챙길 물건의 순서를 정해준 뒤 미리 구한 거리 값을 이용하여 최소 거리를 구해줬습니다.

 

단계 별로 정리하자면 다음과 같습니다.

1. 현재 위치와 챙길 물건들의 위치를 리스트에 저장
2. 리스트를 반복하여 각 위치마다 bfs
   2-1. 이동하면서 현재 위치, 나가는 위치, 다른 물건의 위치를 갈 때마다 거리 저장
3. 순열로 챙길 물건의 순서 정해주기
4. 미리 구한 거리 값을 이용하여 최종 거리 값 구하기
5. 최종 거리 값에서 가장 작은 값 구하기

---

제출 후 3%에서 틀렸습니다 😢

3 3
###
#S#
#E#
1

제가 틀렸던 부분의 반례입니다.

어차피 시작과 끝은 동일하기 때문에 각 물건만 bfs를 돌려줬는데요.

이렇게 물건이 하나도 없을 때는 시작 -> 끝 의 거리를 모르기 때문에 최소 거리가 0이 나왔습니다.

그래서 시작까지 bfs를 돌려주어 시작 -> 끝의 거리를 구해주었고 통과할 수 있었습니다 😎

 

 구현 코드

package BOJ.Gold;

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

public class B17244_아맞다우산 {	
	static int R, C, MIN, select[], dist[][], dir[][] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static char arr[][];
	static boolean visit[][], isSelect[];
	static List<int[]> list = new ArrayList<>();
	static Queue<int[]> queue = new LinkedList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		arr = new char[R][C];
		dist = new int[7][7]; // S + E + X 최대 5개 == 7로 초기화
		list.add(new int[] {0, 0}); // 0번째는 무조건 S
		for (int r=0;r<R;r++) {
			String input = br.readLine();
			for (int c=0;c<C;c++) {
				arr[r][c] = input.charAt(c);
				if (arr[r][c] == 'S') {
					list.get(0)[0] = r; list.get(0)[1] = c;
				} else if (arr[r][c] == 'X') {
					// 사용하기 편리하도록 맵에 번호로 저장
					arr[r][c] = Character.forDigit(list.size(), 10); 
					list.add(new int[] {r, c});
				}
			}
		}
		distSearch(); // 거리 찾기
		select = new int[list.size()-1];
		isSelect = new boolean[list.size()];
		MIN = Integer.MAX_VALUE;
		permutation(0); // 순열
		System.out.println(MIN);
	}
	
	static void permutation(int cnt) {
		if (cnt == list.size()-1) {
			int sum = 0, start = 0; // 출발은 무조건 S부터
			for (int i=0;i<select.length;i++) {
				int now = select[i];
				// 현재 지점 -> 이동 지점까지의 거리 더해주기
				sum += dist[start][now];
				start = now; // 다음 시작 지점은 이동한 지점
			}
			sum += dist[start][list.size()]; // 마지막은 무조건 E
			MIN = Math.min(MIN, sum); // 최소 시간 구하기
			return;
		}
		
		for (int i=1;i<list.size();i++) {
			if (isSelect[i]) continue;
			select[cnt] = i;
			isSelect[i] = true;
			permutation(cnt+1);
			isSelect[i] = false;
		}
	}
	
	static void distSearch() {
		// S부터 구하기 == X가 없을 수도 있으므로 S -> E 까지의 거리도 구함
		for (int i=0;i<list.size();i++) {
			int[] now = list.get(i);
			visit = new boolean[R][C];
			visit[now[0]][now[1]] = true;
			queue.offer(now);
			bfs(i);
 		}
	}
	
	static void bfs(int number) {
		int cnt = 1;
		while(!queue.isEmpty()) {
			int size = queue.size();
			while(size-->0) {
				int[] now = queue.poll();
				for (int d=0;d<4;d++) {
					int nr = now[0] + dir[d][0];
					int nc = now[1] + dir[d][1];
                    			// 범위를 벗어나거나 벽이거나 방문했으면 이동 x
					if (!isIn(nr, nc) || arr[nr][nc] == '#' || visit[nr][nc]) continue;
					
					if (arr[nr][nc] == 'S') {
						// 현재 번호 -> S 까지의 거리 저장
						dist[0][number] = cnt;
						dist[number][0] = cnt;
					} else if (arr[nr][nc] == 'E') {
						// 현재 번호 -> E 까지의 거리 저장
						dist[number][list.size()] = cnt;
						dist[list.size()][number] = cnt;
					} else if (arr[nr][nc] != '.') {
						int next = arr[nr][nc]-'0';
						// 현재 번호 -> 이동 번호까지의 거리 저장
						dist[number][next] = cnt;
						dist[next][number] = cnt;
					}
					visit[nr][nc] = true;
					queue.offer(new int[] {nr, nc});
				}
			}
			cnt++;
		}
	}
	
	static boolean isIn(int nr, int nc) {
		return nr>=0 && nr<R && nc>=0 && nc<C;
	}
}

 

정답!