[BOJ] 백준 17471 - 게리맨더링 풀이

1.  문제

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

17471번: 게리맨더링

2.  풀이 Point

• 링크와스타트 (백준 15661)과 굉장히 유사한 문제이다.
• 주요 입력 자료구조
  • peopleCityMap : 도시 별로 인구수가 저장된 Map
  • List<Integer>[] linkList : 도시 별로 연결되어 있는지를 저장한 연결리스트
  • boolean[] visited : 도시를 2개의 구역으로 나누기 위한 배열

1. N개의 구역이 있을 때, A, B 구역으로 나누는 부분
   • visited 배열의 BackTracking을 통해 True : A 구역, False : B구역으로 판단한다.
2. 구역을 나누었다면 A, B 구역이 연결되어 있는지 확인해야한다.
   • A구역을 담은 Queue와 B구역을 담은 Queue를 만들어 각각 구역을 담는다.
   • isConnected() 안에서 각 구역을 담은 큐를 파라미터로 넘겨주어 BFS 함수를 통해 연결되어 있는지 확인한다.
     • 넘겨받은 큐를 이용하여 BFS 함수를 돌려서 연결 지점을 카운트한다.
     • 이 카운트 수와 큐의 사이즈가 같다면 이는 모든 지점이 연결되었다는 것을 의미한다.
   • 두 지역 모두 연결됨이 확인되었다면 각각 큐에서 꺼내어 합을 구해주고 그 둘의 차를 구하여 result를 갱신한다.
     
     
     

3.  코드

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main {
    static int N; // 도시 수
    static Map<Integer, Integer> peopleCityMap; // 도시 별로 인구수가 저장된 Map
    static List<Integer>[] linkList;  // 도시 별로 연결되어 있는지를 저장한 연결리스트
    static boolean[] visited; // 도시를 2개의 구역으로 나누기 위한 배열 -> true : A구역, false : B구역
    static int result = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	    N = Integer.parseInt(br.readLine());
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    peopleCityMap = new HashMap<>();
	
	    // 맵에 도시 별로 인구수를 저장
	    for (int i = 1; i <= N; i++) {
	        peopleCityMap.put(i, Integer.parseInt(st.nextToken()));
	    }
	
	    // 연결리스트 초기화
	    linkList = new ArrayList[N + 1];
	    for (int i = 1; i <= N; i++) {
	        linkList[i] = new ArrayList<>();
	    }
	
	    // 연결 정보 입력 및 셋팅
	    for (int i = 1; i <= N; i++) {
	        st = new StringTokenizer(br.readLine());
	
	        int cnt = Integer.parseInt(st.nextToken()); // i번째 도시와 인접한 도시의 수
	        for (int j = 0; j < cnt; j++) {
	            int to = Integer.parseInt(st.nextToken());
	
	            linkList[i].add(to);
	            linkList[to].add(i);
	        }
	    }
	
	    // 백트래킹으로 구역 나누기
	    visited = new boolean[N + 1];
	    selectedRange(1, 0);
	
	    // result가 변하지 않았다는 건 구역을 나눌 수 없는 경우이므로 -1을 출력
	    if (result == Integer.MAX_VALUE) {
	        bw.write("-1");
	    } else {
	        bw.write(Integer.toString(result));
	    }
	    bw.flush();
	    bw.close();
	    br.close();
	}

	// 백트래킹으로 구역을 나누기 -> true : A구역, false : B구역
	private static void selectedRange(int depth, int cnt) {
	    if (cnt >= 1 && cnt < N) {
	        Queue<Integer> aQ = new ArrayDeque<>();
	        Queue<Integer> bQ = new ArrayDeque<>();
	
	        for (int i = 1; i <= N; i++) {
	            if (visited[i]) {
	                aQ.add(i);
	            } else {
	                bQ.add(i);
	            }
	        }
	
	        // 둘 다 연결되어 있으면
	        if (isConnected(aQ, true) && isConnected(bQ, false)) {
	        	countMinPeople();
	        }
	    }
	
	    for (int i = depth; i <= N; i++) {
	        if (visited[i]) continue;
	
	        visited[i] = true;
	        selectedRange(i + 1, cnt + 1);
	        visited[i] = false;
	    }
	}
	
	// 구역끼리 연결되어 있는지 판단하는 함수(BFS로 탐색)
	private static boolean isConnected(Queue<Integer> rangeQueue, boolean flag) {
		int rangeSize = rangeQueue.size();
		int cnt = 1;
		
		Queue<Integer> q = new ArrayDeque<>();
		int rp = rangeQueue.poll();
		
		q.add(rp);
		
		boolean[] tempVisited = new boolean[N + 1];
		tempVisited[rp] = true;
		
		while (!q.isEmpty()) {
			int t = q.poll();
			
			if (linkList[t].size() != 0) {
				for (int i = 0; i < linkList[t].size(); i++) {
					if (tempVisited[linkList[t].get(i)]) continue;
					
					if (visited[linkList[t].get(i)] == flag) {
						tempVisited[linkList[t].get(i)] = true;
						q.add(linkList[t].get(i));
						cnt += 1;
					}
				}
			}
		}
		
		if (cnt == rangeSize) {
			return true;
		}
		
		return false;
	}

	// 최소 값 확인 함수
	private static void countMinPeople() {
	    int aCnt = 0;
	    int bCnt = 0;
	    for (int i = 1; i <= N; i++) {
	        if (visited[i]) {
	            aCnt += peopleCityMap.get(i);
	        } else {
	            bCnt += peopleCityMap.get(i);
	        }
	    }
	    result = Math.min(result, Math.abs(aCnt - bCnt));
	}
}

4. 배운점

• BFS를 돌릴 때 인덱스 관리를 잘하자…
  • BFS는 큐에 넣을 때 visited를 방문처리 한다.
    
    
    

5. 점수

80/100