BOJ - 17244 ) 아맞다우산

---

 

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

17244번: 아맞다우산

---

MAP에서 X를 순서대로 방문한 경로중 가장 짧은 것을 출력하는 문제이다.

X의 방문에 순서가 있으므로, NextPermutation을 통하여 다음 순열순서로 X를 탐색한다.

 

1 ) Next Permutation 구현

 

2 ) do while로 전체 순열쌍을 탐색

 

3 ) 가장 작은 경로를 출력한다.

 

추가적으로 백트래킹이 가능할것 같았는데 X의 개수가 최대 5개라 np에서 시간이 많이 들지 않는다고생각했다.

 

+ ) 예외로 X가 없는경우, 단순한 BFS한번만 돌리면 정답이나온다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 아맞다우산 {
	
	public static char [][]map;
	public static int []np;
	public static int answer =2147000000,cnt;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		map = new char[m][n];
		int sy=-1,sx=-1,ex=-1,ey=-1;
		for(int i = 0 ; i < m ; i++) {map[i]= br.readLine().toCharArray();}
		for(int i = 0 ; i < m ; i++) {
			for(int j = 0 ; j < n ; j++) {
				if(map[i][j] =='X') cnt++;
				if(map[i][j] =='S') {sy = i ; sx = j; map[i][j]='.';}
				if(map[i][j] =='E') {ey = i ; ex = j;}
			}
		}
		
		int mapping[][] = new int[cnt+1][2];
		int c = 1;
		for(int i = 0 ; i < m ; i++) {
			for(int j = 0 ; j < n ; j++) {
				if(map[i][j]=='X') {
					mapping[c][0] = i;
					mapping[c][1] = j;
					c++;
				}
			}
		}
		ArrayDeque<int []> dq = new ArrayDeque<>();
		int ans =0;
		int visitflag =1;
		int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
		if( c ==1) { // 예외처리 챙길 물건이 없는경우
			int visit[][] = new int[m][n];
			dq.add(new int[] {sy,sx,0});
			while(!dq.isEmpty()) {
				int now[] = dq.poll();
				if(map[now[0]][now[1]]=='E') {
					answer = now[2];
					dq.clear();
					break;
				}
				for(int j = 0 ;j < 4 ; j++) {
					int nexty = now[0] +dir[j][0];
					int nextx = now[1] +dir[j][1];
					if(nexty >=0 && nextx >= 0 && nexty < m && nextx< n && map[nexty][nextx]!='#' &&visit[nexty][nextx] != visitflag) {
						visit[nexty][nextx] = visitflag;
						dq.add(new int[] {nexty , nextx , now[2]+1});
					}
				}
			}
		} else {
			// 'X'를 1,2,3,4에 매핑하고 순서대로 bfs
			np = new int[cnt]; for(int i = 1 ; i <= cnt ; i++) np[i-1] =i;
			do {
				dq.add(new int[] {sy,sx,0});
				int visit[][] = new int[m][n];
				ans=0;
				for(int i = 0 ; i < cnt; i++) {
					// mapping에 np[i]번째를 찾아떠난ㄴ다..
					while(!dq.isEmpty()) {
						int now[] = dq.poll();
						if(now[0] == mapping[np[i]][0] && now[1] == mapping[np[i]][1]) {
							ans += now[2];
							dq.clear();
							break;
						}
						for(int j = 0 ;j < 4 ; j++) {
							int nexty = now[0] +dir[j][0];
							int nextx = now[1] +dir[j][1];
							if(nexty >=0 && nextx >= 0 && nexty < m && nextx< n && map[nexty][nextx]!='#' &&visit[nexty][nextx] != visitflag) {
								visit[nexty][nextx] = visitflag;
								dq.add(new int[] {nexty , nextx , now[2]+1});
							}
						}
					} 
					visitflag++; dq.add(new int[] {mapping[np[i]][0] , mapping[np[i]][1] , 0});
				}
				while(!dq.isEmpty()) {
					int now[] = dq.poll();
					if(map[now[0]][now[1]]=='E') {
						ans += now[2];
						dq.clear();
						break;
					}
					for(int j = 0 ;j < 4 ; j++) {
						int nexty = now[0] +dir[j][0];
						int nextx = now[1] +dir[j][1];
						if(nexty >=0 && nextx >= 0 && nexty < m && nextx< n && map[nexty][nextx]!='#' &&visit[nexty][nextx] != visitflag) {
							visit[nexty][nextx] = visitflag;
							dq.add(new int[] {nexty , nextx , now[2]+1});
						}
					}
				}
				answer = answer > ans ? ans : answer;
			}while(nextper());
		}
		System.out.println(answer);
	}
	
	private static boolean nextper() {
		int i = cnt -1;
		while( i > 0 && np[i-1] > np[i]) i--;
		if(i==0)return false;
		int k = cnt -1;
		while(np[i-1] >= np[k]) k--;
		int temp = np[i-1];
		np[i-1] = np[k];
		np[k] = temp;
		 k = cnt -1;
		 while( i < k) {
				temp =np[i];
				np[i]= np[k];
				np[k] =temp;
				i++;--k;
		 }
		return true;
	}
}

---