정범의 프로그래밍 블로그 입니다.

5 분 소요

1. 문제 접근 방법 및 순서

이 문제는 최단 경로 탐색과 순열, 그리고 조건부 방문이 결합된 시뮬레이션 및 최적화 문제입니다. 외판원 순회 문제의 변형이라고 할 수 있습니다.

  1. 데이터 구조화
    • 맵을 탐색하면서 몬스터(양수)와 고객(음수)의 위치 정보를 저장합니다.
    • 이때, 몬스터 k와 고객 -k를 쉽게 매칭할 수 있도록 인덱싱합니다.
  2. 핵심 조건 파악
    • 몬스터를 잡기 전에는 해당 고객을 방문해도 의미가 없다는 것이 가장 중요합니다.
    • 방문 순서에 선행 관계가 존재합니다.
  3. 거리 행렬 계산
    • 시작점, 모든 몬스터, 모든 고객 간의 거리를 미리 계산해두면 매번 계산할 필요가 없어 효율적입니다.
    • 거리 계산은 맨해튼 거리를 사용합니다.
  4. 모든 가능한 경로 탐색
    • 몬스터와 고객의 총합은 최대 8입니다.
    • 이들의 방문 순서를 결정하는 모든 경우의 수를 탐색하되, 조건을 만족하는지 확인합니다.
  5. 최솟값 갱신
    • 모든 임무를 완수한 시점의 총 이동 시간 중 가장 작은 값을 찾습니다.


2. 문제 해결에 필요한 개념 및 알고리즘

  1. 완전 탐색
    • 지점 방문 순서에 따라 결과가 판이하게 달라집니다.
    • 지점 수가 8!이므로 충분히 제한 시간 내에 풀 수 있습니다.
  2. 맨해튼 거리
    • 격자판에서 상하좌우로만 이동하며, 1칸 이동에 1시간이 걸린다고 명시되어 있습니다.
    • dist = Math.abs(x1-x2)+Math.abs(y1-y2)
  3. 상태 관리
    • 어떤 몬스터를 잡았는지, 어떤 고객을 방문했는지 체크해야 중복 방문을 막고 선행 조건을 확인할 수 있습니다.


3. 어려웠던 점

  • 몬스터와 고객의 선행 관계를 코드로 어떻게 구현하는지 방법을 몰랐습니다.
  • 고객을 방문하려고 할 때, 해당 번호의 몬스터를 이미 방문했는가?를 체크하는 로직이 필요합니다.


4. 코드 풀이

4.1 데이터 구조화

4.1.1 Pos 클래스

static class Pos {
    int r, c, num;
    Pos(int r, int c, int num) {
        super();
        this.r = r;
        this.c = c;
        this.num = num;
    }
}

static List<Pos> list; // 고객, 몬스터 리스트
  • 고객, 몬스터 위치, 정보를 저장하는 클래스를 선언합니다.
  • 고객, 몬스터 정보를 담는 리스트를 선언합니다.

4.1.2 몬스터 포획 체크

static boolean[] checkMonster; // 몬스터 포획 체크

// 맵의 정보 입력
for (int i = 1; i <= N; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	for (int j = 1; j <= N; j++) {
		int val = Integer.parseInt(st.nextToken());

	// 고객이나 몬스터가 아니면 다음으로 넘어간다.
	if (val == 0)
	    continue;

	// 고객 또는 몬스터를 리스트에 추가
    list.add(new Pos(i, j, val));

	// 몬스터의 수 측정
	if (val > 0)
		Mcnt++;
    }
}

// 몬스터 포획 체크 초기화
checkMonster = new boolean[Mcnt + 1];
  • 몬스터와 고객의 선행 관계를 체크하는데 사용합니다.
  • 몬스터 포획 체크 배열을 초기화합니다.
  • 맵에서 입력된 몬스터의 개수로 체크합니다.
  • 1 ~ 모든 몬스터 수 만큼 초기화합니다.

4.2 맨해튼 거리 계산

// 헌터와 방문 장소의 거리 계산
int dist = Math.abs(r - pos.r) + Math.abs(c - pos.c);
  • 헌터와 방문 장소의 거리를 계산합니다.

4.3 최소값 갱신

// 종료 조건
if (level == list.size()) {
	result = Math.min(result, curdist);
	return;
}
  • 모든 임무를 완수한 시점의 총 이동 시간 중 가장 작은 값을 갱신합니다.

4.4 DFS 함수 코드

static void dfs(int r, int c, int curdist, int level) {

	// 종료 조건
	if (level == list.size()) {
		result = Math.min(result, curdist);
		return;
	}

	// 경우의 수 수행
	for (int i = 0; i < list.size(); i++) {

		// 이미 방문한 곳은 다음으로 넘긴다.
		if (visited[i])
			continue;

		// 현재 선택된 원소
		Pos pos = list.get(i);

		// 고객인지 경우
		if (pos.num < 0) {
			// 고객에 해당하는 몬스터 번호
			int monidx = Math.abs(pos.num);

			// 고객의 몬스터를 포획하지 못하면 다음으로 넘어간다.
			if (checkMonster[monidx] == false)
				continue;
		}

		// 몬스터인 경우 포획 체크
		if (pos.num > 0) {
			checkMonster[pos.num] = true;
		}

		// 현재 방문 체크
		visited[i] = true;

		// 헌터와 방문 장소의 거리 계산
		int dist = Math.abs(r - pos.r) + Math.abs(c - pos.c);

		// 다음 방문 이동
		dfs(pos.r, pos.c, curdist + dist, level + 1);

		// 포획 체크 해제
		if (pos.num > 0) {
			checkMonster[pos.num] = false;
		}

		// 현재 방문 체크 해제
		visited[i] = false;

	}
} // dfs 종료

4.5 전체 코드

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

public class Solution {

	static int N; // 맵의 크기
	static boolean[] checkMonster; // 몬스터 포획 체크
	static List<Pos> list; // 고객, 몬스터 리스트
	static boolean[] visited; // 방문 체크 배열
	static int result; // 모든 몬스터를 사냥하고 확인받는데 걸리는 가장 빠른 시간

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine().trim());

		// tc 수행
		for (int tc = 1; tc <= T; tc++) {

			// 맵의 크기 입력
			N = Integer.parseInt(br.readLine().trim());
			list = new ArrayList<>();
			result = Integer.MAX_VALUE;

			int Mcnt = 0; // 몬스터의 수

			// 맵의 정보 입력
			for (int i = 1; i <= N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 1; j <= N; j++) {
					int val = Integer.parseInt(st.nextToken());

					// 고객이나 몬스터가 아니면 다음으로 넘어간다.
					if (val == 0)
						continue;

					// 고객 또는 몬스터를 리스트에 추가
					list.add(new Pos(i, j, val));

					// 몬스터의 수 측정
					if (val > 0)
						Mcnt++;
				}
			}

			// 몬스터 포획 체크 초기화
			checkMonster = new boolean[Mcnt + 1];

			// 방문 체크 배열 초기화
			visited = new boolean[list.size()];

			// 처리
			dfs(1, 1, 0, 0);

			// 출력 내용 추가
			sb.append("#" + tc + " " + result + "\n");
		} // tc 종료

		// 출력
		System.out.println(sb);

	}

	// 헌터의 사냥 및 보고 기능 수행 함수
	// 현재 헌터의 좌표, 현재 거리, 다음 깊이
	static void dfs(int r, int c, int curdist, int level) {

		// 종료 조건
		if (level == list.size()) {
			result = Math.min(result, curdist);
			return;
		}

		// 경우의 수 수행
		for (int i = 0; i < list.size(); i++) {

			// 이미 방문한 곳은 다음으로 넘긴다.
			if (visited[i])
				continue;

			// 현재 선택된 원소
			Pos pos = list.get(i);

			// 고객인지 경우
			if (pos.num < 0) {
				// 고객에 해당하는 몬스터 번호
				int monidx = Math.abs(pos.num);

				// 고객의 몬스터를 포획하지 못하면 다음으로 넘어간다.
				if (checkMonster[monidx] == false)
					continue;
			}

			// 몬스터인 경우 포획 체크
			if (pos.num > 0) {
				checkMonster[pos.num] = true;
			}

			// 현재 방문 체크
			visited[i] = true;

			// 헌터와 방문 장소의 거리 계산
			int dist = Math.abs(r - pos.r) + Math.abs(c - pos.c);

			// 다음 방문 이동
			dfs(pos.r, pos.c, curdist + dist, level + 1);

			// 포획 체크 해제
			if (pos.num > 0) {
				checkMonster[pos.num] = false;
			}

			// 현재 방문 체크 해제
			visited[i] = false;

		}
	} // dfs 종료

	static class Pos {
		int r, c, num;

		public Pos(int r, int c, int num) {
			super();
			this.r = r;
			this.c = c;
			this.num = num;
		}

	}

}

카테고리:

업데이트:

참고

[모의 SW 역량테스트] 디저트 카페 공부

2 분 소요

1. 문제 접근 방법 및 접근 순서 이 문제는 임의의 한 지점에서 출발해 사각형 모양을 그리며 제자리로 돌아오는 경로 중, 중복되는 디저트 종류 없이 가장 많은 디저트를 먹는 경로를 찾는 것이 핵심입니다.

사칙연산 유효성 검사

1 분 소요

1. 문제 접근 방법 및 순서 핵심 아이디어 연산자(+,-,*,/): 반드시 자식 노드를 가집니다. 숫자: 자식 노드가 없는 단말 노드여야 합니다.