[SWEA/Java] 7208. 지도 칠하기

[SWEA/Java] 7208. 지도 칠하기

SW Expert Academy

---

문제 해석

이 문제는 지도의 각 국가에 4가지 색 중 하나를 칠하되, 인접한 국가는 서로 다른 색으로 칠해야 한다. 초기 상태로 일부 국가들은 이미 색칠되어 있으며, 최소한의 변경으로 모든 조건을 만족하도록 색을 칠하는 방법을 찾아야 한다.

풀이 과정

1. 입력으로 국가의 수, 현재 색상 정보, 그리고 국가 간 인접 정보를 받는다.
2. 가능한 모든 색상 변경 조합을 생성하여 최소 변경 횟수를 찾는다.
3. 이를 위해 재귀적으로 순열을 생성하며, 각 순열에 대해 조건을 만족하는지 확인한다.
4. 인접한 국가들이 서로 다른 색을 가지고 있는지 검사하고, 필요한 최소 변경 횟수를 갱신한다.

코드

package edu.ssafy.im.SWEA.D4.No7208;

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

public class Solution {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Solution().io();
	}

	private int n;  // 국가의 수
	private int[] arr;  // 각 국가의 현재 색상
	private List<ArrayList<Integer>> graph;  // 국가 간 인접 리스트
	private int[] sel;  // 순열 생성용 배열

	private void io() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());  // 테스트 케이스 수
		for (int t = 1; t <= T; t++) {
			n = Integer.parseInt(br.readLine());

			arr = new int[n];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());  // 현재 색상 입력 받기
			}

			graph = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				graph.add(new ArrayList<Integer>());
			}
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					if (st.nextToken().charAt(0) == '1') {
						graph.get(i).add(j);  // 인접 국가 정보 추가
					}
				}
			}
			sb.append("#").append(t).append(" ").append(sol()).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private int sol() {
		int ans = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			sel = new int[i];
			if (permutation(0, 0)) {  // 가능한 순열을 모두 시도
				ans = i;
				break;
			}
		}
		return ans;  // 최소 변경 횟수 반환
	}
	
	private boolean check(int k, int v, int[] tmp) {  // 변경 후 인접 국가들이 서로 다른 색을 가지는지 검사
		if (k == sel.length) {
			int[] tmp2 = arr.clone();
			
			for(int i = 0; i < sel.length; i++) {
				tmp2[sel[i]] = tmp[i];  // 새로운 색상 적용
			}
			
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < graph.get(i).size(); j++) {
					if (tmp2[graph.get(i).get(j)] == tmp2[i]) {
						return false;  // 인접 국가가 같은 색을 가지면 false
					}
				}
			}
			return true;
		}

		for (int i = 1; i <= 4; i++) {  // 모든 색상을 시도
			if ((v & (1 << i)) == 0) {
				tmp[k] = i;
				if(check(k + 1, v | 1 << i, tmp)) {
					return true;  // 모든 조건을 만족하면 true
				}
			}
		}
		
		return false;
	}

	private boolean permutation(int k, int v) {  // 순열 생성
		if (k == sel.length) {
			if (check(0, 0, new int[sel.length])) {
				return true;	
			}
			return false;
		}

		for (int i = 0; i < n; i++) {
			if ((v & (1 << i)) == 0) {
				sel[k] = i;
				if(permutation(k + 1, v | 1 << i))
					return true;
			}
		}

		return false;
	}
}

시간 복잡도 분석

이 알고리즘은 국가의 수 n과 깊이 i에 따라 순열을 생성하고 각 순열에 대해 검증하는 과정이 포함된다. 최악의 경우, 모든 국가에 대해 모든 색상 변경의 조합을 검토해야 하므로 시간 복잡도는 O(n⋅n!) 이 될 수 있다.

느낀점

이 문제는 그래프 색칠 문제의 변형으로, 주어진 초기 상태에서 최소한의 변경으로 문제의 요건을 만족해야 한다는 점에서 도전적이었다. 모든 가능한 색상 조합을 시도하면서 해를 찾아야 하는 점이 흥미롭고, 효율적인 방법을 찾기 위한 노력이 필요하다.