DeJa
Techvu
DeJa
전체 방문자
51,021
오늘
19
어제
54
  • Techvu (60)
    • DesignPatterns (3)
      • 생성 (0)
      • 구조 (1)
      • 행동 (2)
    • Refactoring (0)
    • DataStructures (0)
    • Algorithms (24)
      • 기본 지식 (12)
      • 문제 풀이 (12)
    • OOP (0)
    • TDD (2)
    • DDD (0)
    • Programming Languages (9)
      • Java (9)
      • Kotlin (0)
    • Spring (1)
    • JPA (7)
    • Web (1)
      • 기본 지식 (1)
      • 실무 경험 (0)
    • CS (12)
      • Network (1)
      • OS (8)
      • DataBase (3)
      • Server (0)
    • Git (1)
    • Conferences (0)

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

  • Study
  • GitHub
  • Medium Blog

인기 글

  • 스키마(Schema)
    2022.01.08
    스키마(Schema)
  • 자바 버전별 역사 및 특징
    2022.01.12
    자바 버전별 역사 및 특징
  • 깃허브 사용 방법
    2021.12.15
    깃허브 사용 방법
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • JPA 는 과연 1차 캐시를 통해서 Repeatable R⋯
    2021.12.27
    JPA 는 과연 1차 캐시를 통해서 Repeatable R⋯

태그

  • network
  • Spring
  • 알고리즘
  • JPA
  • OS
  • web
  • java
  • 디자인패턴
  • CS
  • DATABASE
  • TDD

최근 댓글

  • 글 잘읽고 가요.
    아이폰
  • 컴파일러자체에서 꼬리재귀를 지원하지 않으니 static으로⋯
    aaa
  • 압도적 감사
    ㅇㅇㅇ

최근 글

  • Write a test code right now
    2022.03.24
    Write a test code right now
  • 동시성 이슈(Concurrency Issue)
    2022.03.20
    동시성 이슈(Concurrency Issue)
  • POJO, JavaBean, Entity, VO, DTO
    2022.02.08
    POJO, JavaBean, Entity, VO, DTO
  • TDD with Agile
    2022.02.05
    TDD with Agile
  • Java Stream 기초
    2022.01.23
    Java Stream 기초

티스토리

hELLO · Designed By 정상우.
DeJa

Techvu

[BOJ 16234] 인구 이동
Algorithms/문제 풀이

[BOJ 16234] 인구 이동

2021. 12. 31. 16:39
728x90

인구 이동

BOJ 16234 : 인구 이동

해설

이 문제는 2차원 배열의 탐색 문제이기 때문에 좌표 형태를 그래프로 바꿔야 한다는 생각을 먼저 하였다.

문제의 입력 예시 4번을 가지고 해설할 것이다.

입력

N : 3, L : 5, R : 10

3 5 10
10 15 20
20 30 25
40 22 10

L <= 인구차이(P) <= R

5 <= p <= 10

(x, y) : 나라 - or | : 국경선, # : 인구수

(0, 0 #10) (0, 1 #15) (0, 2 #20)

(1, 0 #20) (1, 1 #30) (1, 2 #25)

(2, 0 #40) (2, 1 #22) (2, 2 #10)

입력 예시를 좌표 형태로 나타내면 위와 같다.

이 상태에서, 인접한 나라들을 탐색하여 국경선을 열 수 있는지 확인해야 한다. 즉, 인접한 두 나라의 인구차이가 L 명 이상 R 명 이하라면 두 나라가 공유하는 국경선을 하루동안 열 수 있다.

인접한 나라를 탐색하기 위해서는 상,하,좌,우 로 탐색하면 된다.

// 상하좌우 : 인접한 나라를 판단하기 위함
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, 1, -1};

인접한 나라들을 탐색하기 위해서 BFS 방법을 사용하면 된다.

(0, 0) 에 위치한 나라를 시작으로 인접한 나라를 탐색하면 된다.

첫 번째 BFS 탐색 결과 : 첫 번째 연합

(0, 0 #10)-(0, 1 #15)-(0, 2 #20)
  |                       |
(1, 0 #20)-(1, 1 #30)-(1, 2 #25)
                |
           (2, 1 #22)

위 그래프 형태가 첫 번째 연합의 결과이다. 따라서 인구 이동이 1번 일어난다. 인구 이동이 일어난 후에는 연합간의 인구를 균등 분배 해야 하므로 문제에서 주어진 식대로 계산하면 아래와 같다.

  • 연합을 이루고 있는 각 칸의 인구수 = 연합의 인구수 / 연합을 이루고 있는 칸의 개수
    • 142(10 + 15 + 20 + 20 + 22 + 25 + 30) / 7 = 20

인구 이동

(0, 0 #20)-(0, 1 #20)-(0, 2 #20)
  |                       |
(1, 0 #20)-(1, 1 #20)-(1, 2 #20)
                |
           (2, 1 #20)

따라서, 연합의 인구수를 계산하기 위한 변수와, 칸의 개수를 나타내는 변수가 필요하다는 것을 알 수 있다. 또한, 연합에 속하는 나라들을 저장하기 위한 자료구조도 필요하다.

BFS 탐색 결과 현재 국경선으로 연결되어 있는 나라들은 방문(Visited) 한 나라들이므로, 다음 BFS 탐색 때 방문 여부를 체크하여 인구 이동이 더 이상 일어나지 않을 때 까지 반복하면 된다.

모든 국경선 닫고, 방문 여부 체크

(0, 0 #20, VISITED) (0, 1 #20 , VISITED) (0, 2 #20 , VISITED)

(1, 0 #20, VISITED) (1, 1 #20 , VISITED) (1, 2 #20 , VISITED)

(2, 0 #40) (2, 1 #20, VISITED) (2, 2 #10)

두 번째 BFS 탐색의 시작은 방문하지 않은 나라 중 가장 빠른 (3, 1) 부터 탐색이 시작될 것이다.

두 번째 연합

             (1, 2 #20)
                 |
(2, 1 #20) - (2, 2 #10)

인구 이동

             (1, 2 #16)
                 |
(2, 1 #16) - (2, 2 #16)

최종 결과 : 더 이상 연합이 불가능하므로 종료

(0, 0 #20) (0, 1 #20) (0, 2 #20)

(1, 0 #20) (1, 1 #20) (1, 2 #16)

(2, 0 #40) (2, 1 #16) (2, 2 #16)

정리

  • 2차원 배열의 탐색 문제 -> 그래프
  • 입력 값을 배열 형태의 그래프로 표현
  • 인접한 나라들을 탐색하기 위해 BFS 알고리즘 이용
  • 첫 번째 연합 결과 = 인구 이동
    • 연합의 횟수 = 인구 이동의 횟수
  • 연합 > 인구 이동 > 연합한 나라들의 인구 수를 재계산 > 인구 이동이 불가능 할 때 까지 반복

구현

class Country {

    private int x;
    private int y;

    public Country(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

public class Main {

    private static int N;
    private static int L;
    private static int R;
    private static int[][] graph; // (x, y) 나라, 저장된 값은 인구수
    private static boolean[][] visited; // 방문 처리 여부
    private static List<Country> unitedCountries; // 연합된 나라들
    private static int unitedCount = 0; // 연합한 나라의 개수
    private static int sumOfPopulationInUnitedCountry = 0; // 연합한 나라들의 인구수 합
    private static int answer = 0; // 인구 이동이 일어난 횟수

    // 상하좌우 : 인접한 나라를 판단하기 위함
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) {
        input();
        solution();
        System.out.println(answer);
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        L = sc.nextInt();
        R = sc.nextInt();

        // 그래프, 방문처리여부 초기화
        graph = new int[N][N];

        // 인구수 저장
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < N; k++) {
                graph[i][k] = sc.nextInt();
            }
        }
    }

    // 인구이동이 발생하지 않을 때 까지 반복
    private static void solution() {
        while(true) {
            boolean isMoved = false;
            visited = new boolean[N][N];
            for (int x = 0; x < N; x++) {
                for (int y = 0; y < N; y++) {
                    if(!visited[x][y]) { // uniteByBfs 를 통해 방문처리 된 인접리스트들에 대해서도 생략
                        unite(x, y);
                        if(unitedCountries.size() > 1) {
                            move();
                            answer++;
                            isMoved = true;
                        }
                    }
                }
            }
            if(!isMoved) {
                break;
            }
        }
    }

    private static void unite(int x, int y) {
        Queue<Country> Q = new LinkedList<>();
        unitedCountries = new ArrayList<>();

        Country start = new Country(x, y);
        Q.offer(start);
        unitedCountries.add(start);
        visited[x][y] = true;

        // 연합한 나라의 개수 : 자기 자신으로 초기화
        unitedCount = 1;
        // 연합한 나라의 인구수 합 탐색 대상인 나라의 인구수로 초기화
        sumOfPopulationInUnitedCountry = graph[x][y];
        while(!Q.isEmpty()) {
            Country country = Q.poll();
            x = country.getX();
            y = country.getY();
            int p1 = graph[x][y];
            // 상하좌우 탐색
            for (int i = 0; i < dx.length; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if((nx >= 0 && ny >= 0 && nx < N && ny < N) && !visited[nx][ny]) {
                    int p2 = graph[nx][ny];
                    if(isLinkable(p1, p2)) {
                        Country adjacentCountry = new Country(nx, ny);
                        // 연결 가능한 인접한 나라를 Q 에 넣는다.
                        Q.offer(adjacentCountry);
                        // 연합한 나라를 보관하는 리스트에 넣는다.
                        unitedCountries.add(adjacentCountry);
                        // 연합한 나라의 인구수 합 누적
                        sumOfPopulationInUnitedCountry += p2;
                        // 연합한 나라의 개수 증가
                        unitedCount++;
                        // 방문 처리
                        visited[nx][ny] = true;
                    }
                }
            }
        }
    }

    // 연결 가능한지
    private static boolean isLinkable(int p1, int p2) {
        int absValue = Math.abs(p1 - p2);
        return L <= absValue && absValue <= R;
    }

    // 인구 이동, 연합한 나라들의 인구수를 재계산
    private static void move() {
        for(Country country : unitedCountries) {
            graph[country.getX()][country.getY()] = sumOfPopulationInUnitedCountry / unitedCount;
        }
    }
}
728x90
저작자표시 비영리 동일조건
  • 카카오스토리
  • 트위터
  • 페이스북

'Algorithms > 문제 풀이' 카테고리의 다른 글

[BOJ 14502] 연구소  (0) 2022.01.06
[BOJ 15686] 치킨 배달  (0) 2022.01.03
[BOJ 1715] 카드 정렬하기  (0) 2021.12.18
[BOJ 18352] 특정 거리의 도시 찾기  (0) 2021.12.18
[BOJ 3190] 뱀  (0) 2021.12.18
    'Algorithms/문제 풀이' 카테고리의 다른 글
    • [BOJ 14502] 연구소
    • [BOJ 15686] 치킨 배달
    • [BOJ 1715] 카드 정렬하기
    • [BOJ 18352] 특정 거리의 도시 찾기
    알고리즘
    DeJa
    DeJa
    Tech Blog
    댓글쓰기
    [BOJ 15686] 치킨 배달
    다음 글
    [BOJ 15686] 치킨 배달
    [BOJ 1715] 카드 정렬하기
    이전 글
    [BOJ 1715] 카드 정렬하기

    티스토리툴바