백준 17244번 - 아맞다우산 java
문제
경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다.
"아 맞다 우산!!!"
경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다.
외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.
평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다.
경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.
경재 씨를 위해 집을 위에서 바라본 모습과 챙겨야 할 물건들의 위치들을 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.
입력
첫 번째 줄에는 집의 가로 길이 N과 세로 길이 M이 입력된다. (3 ≤ N, M ≤ 50)
두 번째 줄부터는 집의 구조가 예제 입력과 같이 주어진다.
비어있는 곳은 '.'로 벽은 '#'로 입력된다. 경재 씨의 현재 위치는 S, 나가는 문의 위치는 E, 챙겨야 하는 물건은 종류에 상관없이 X로 입력된다.
챙겨야 하는 물건은 최대 5개까지 있을 수 있다. 집은 언제나 벽으로 둘러싸여 있고, 나가는 문은 언제나 하나이다.
출력
S에서 출발하여 모든 물건을 챙겨서 E까지 도착할 수 있는 최소 시간을 출력한다. 모든 물건을 챙길 수 없는 경우는 주어지지 않는다.
해결 방법
맵의 크기는 최대 50 * 50이고, 챙겨야 하는 물건의 개수는 최대 5개다.
출발점에서 시작해서 모든 물건을 방문한다음, 마지막 물건 지점에서 도착점까지의 거리를 구하면 된다.
따라서 어떤 순서로 물건을 방문할지가 중요한데, 물건이 5개라 했을 때 가능한 경우의 수는 5*4*3*2*1 으로 120가지가 나온다.
모든 방문순서를 고려하며, 최단거리를 구하면 된다.
각 정점에서 다른 정점까지의 거리 구하기
일단 출발점을 0번 정점이라고 하고, 각 물건을 1번부터 최대 5번 정점, 출구를 6번 정점이라고 가정해보자
그러면 예제의 경우 다음과 같은 map 이 나오게 된다
7 6
#######
#01..2#
#..####
#..3..#
#...4.#
#####6#
이제 map 을 돌면서 각 정점에서 다른 정점까지의 거리를 인접 리스트 형식으로 구해보자.
static void initEdge(int N, int M) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == START) {
bfs(new Point(j, i), N, M, 0);
} else if (map[i][j] >= 1 && map[i][j] <= 5) {
bfs(new Point(j, i), N, M, map[i][j]);
}
}
}
}
맵을 전부 탐색하면서, 지금 보는 좌표가 시작점이거나 챙겨야 하는 물건일 경우, 해당 좌표에서 다른 물건이나 도착점까지의 거리를 bfs로 구한다.
static void bfs(Point startPoint, int N, int M, int start) {
Queue<Point> points = new LinkedList<>();
points.add(startPoint);
boolean[][] visited = new boolean[N][M];
visited[startPoint.y][startPoint.x] = true;
int length = 0;
while (!points.isEmpty()) {
int size = points.size();
for (int i = 0; i < size; i++) {
Point temp = points.poll();
for (int[] move : dxDy) {
int X = temp.x + move[0];
int Y = temp.y + move[1];
if (!visited[Y][X]) {
if (map[Y][X] >= 1 && map[Y][X] <= 5) {
visited[Y][X] = true;
adjacentList[start].add(new Edge(map[Y][X], length + 1));
points.add(new Point(X, Y));
} else if (map[Y][X] == EXIT) {
visited[Y][X] = true;
adjacentList[start].add(new Edge(6, length + 1));
} else if (map[Y][X] != WALL) {
visited[Y][X] = true;
points.add(new Point(X, Y));
}
}
}
}
length++;
}
}
여기서 간선을 생성할 때, 도착점에서 다른 곳으로의 간선이랑, 챙겨야 하는 물건 에서 출발지점까지의 간선은 구하지 않는 경우를 주목하자. 도착점에 도달할 경우 다른 지점으로 갈 필요가 없고, 출발점에서 출발해서 다시 돌아가야할 필요는 없기 때문이다.
챙겨야 하는 물건의 모든 방문 순서를 고려하여 최소 거리 찾기
이제 시작점에서 각 챙겨야 하는 물건까지의 거리와, 물건에서 도착점까지의 거리를 구했으므로, 모든 방문순서 조합을 고려하여 최소 길이를 찾아준다.
static void solution(int totalCount, int index, int length, boolean[] use, int to) {
//모든 물건을 다 챙겼다면, 현재 위치에서 도착점까지의 거리를 구해준다.
if (totalCount == index) {
for (Edge edge : adjacentList[to]) {
if (edge.to == 6) {
min = Math.min(length + edge.weight, min);
return;
}
}
}
//각 순서별로 무엇을 고를지를 전부 고려한다.
for (Edge edge : adjacentList[to]) {
if (edge.to != 6 && !use[edge.to]) {
use[edge.to] = true;
solution(totalCount, index + 1, length + edge.weight, use, edge.to);
use[edge.to] = false;
}
}
}
전체 코드
public class P17244 {
static final char EXIT = 'E';
static final char EMPTY = '.';
static final char START = 'S';
static final char MUST_HAVE = 'X';
static final char WALL = '#';
static int[][] map;
static final int[][] dxDy = {{-1, 0,}, {0, -1}, {1, 0}, {0, 1}};
static final ArrayList<Edge>[] adjacentList = new ArrayList[6];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(in));
StringBuilder sb = new StringBuilder();
StringTokenizer mapInfo = new StringTokenizer(br.readLine());
int number = 0;
int M = Integer.parseInt(mapInfo.nextToken());
int N = Integer.parseInt(mapInfo.nextToken());
for (int i = 0; i < 6; i++) adjacentList[i] = new ArrayList<>();
map = new int[N][M];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = input.charAt(j);
if (map[i][j] == MUST_HAVE) {
map[i][j] = ++number;
}
}
}
initEdge(N, M);
solution(number, 0, 0, new boolean[6], 0);
System.out.println(min);
}
static int min = Integer.MAX_VALUE;
static void solution(int totalCount, int index, int length, boolean[] use, int to) {
if (totalCount == index) {
for (Edge edge : adjacentList[to]) {
if (edge.to == 6) {
min = Math.min(length + edge.weight, min);
return;
}
}
}
for (Edge edge : adjacentList[to]) {
if (edge.to != 6 && !use[edge.to]) {
use[edge.to] = true;
solution(totalCount, index + 1, length + edge.weight, use, edge.to);
use[edge.to] = false;
}
}
}
static void initEdge(int N, int M) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == START) {
bfs(new Point(j, i), N, M, 0);
} else if (map[i][j] >= 1 && map[i][j] <= 5) {
bfs(new Point(j, i), N, M, map[i][j]);
}
}
}
}
static void bfs(Point startPoint, int N, int M, int start) {
Queue<Point> points = new LinkedList<>();
points.add(startPoint);
boolean[][] visited = new boolean[N][M];
visited[startPoint.y][startPoint.x] = true;
int length = 0;
while (!points.isEmpty()) {
int size = points.size();
for (int i = 0; i < size; i++) {
Point temp = points.poll();
for (int[] move : dxDy) {
int X = temp.x + move[0];
int Y = temp.y + move[1];
if (!visited[Y][X]) {
if (map[Y][X] >= 1 && map[Y][X] <= 5) {
visited[Y][X] = true;
adjacentList[start].add(new Edge(map[Y][X], length + 1));
points.add(new Point(X, Y));
} else if (map[Y][X] == EXIT) {
visited[Y][X] = true;
adjacentList[start].add(new Edge(6, length + 1));
} else if (map[Y][X] != WALL) {
visited[Y][X] = true;
points.add(new Point(X, Y));
}
}
}
}
length++;
}
}
static class Edge {
int to;
int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
}