반응형
* 핵심
삼성기출중 쉬운편에 속하는 문제이다.
2중 For문을 돌면서 BFS로 탐색하면 된다.
문제에서 설명이 조금 애매한데, 몇 번이라기보다는 몇 일이 걸린다고 이해하는게 편하다.
하루에 인구 이동한 나라는 그 날은 또 다른 나라랑 연합을 맺을 수 없다.
문제에 주어진 마지막 예시를 보면,
1일차
2일차
3일차
위 예제를 보면 6번의 인구 이동이 있지만 3일에 걸쳐 인구 이동되었기 때문에 3을 출력하는 것이 맞다.
* 문제
문제
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.
오늘부터 인구 이동이 시작되는 날이다.
인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.
- 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
- 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
- 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
- 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
- 연합을 해체하고, 모든 국경선을 닫는다.
각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)
둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)
인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.
출력
인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.
* 소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | import java.io.*; import java.util.*; public class Main { public static StringTokenizer stk; public static StringBuilder sb = new StringBuilder(); public static int[] dx = {1, -1, 0, 0}; public static int[] dy = {0, 0, 1, -1}; public static int min, max, ans = 0; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); stk = new StringTokenizer(br.readLine()); int n = Integer.parseInt(stk.nextToken()); min = Integer.parseInt(stk.nextToken()); max = Integer.parseInt(stk.nextToken()); int[][] map = new int[n + 1][n + 1]; boolean[][] visited = new boolean[n + 1][n + 1]; for (int i = 1; i <= n; i++) { stk = new StringTokenizer(br.readLine()); for (int j = 1; j <= n; j++) { map[i][j] = Integer.parseInt(stk.nextToken()); } } boolean hasMoreMoving = false; //while문에서 인구이동 발생 여부 확인 while (!hasMoreMoving) { Queue<Pair> q = new LinkedList<>(); int sum = 0, cnt = 0; //sum = 인구 이동할 나라의 사람수, cnt = 인구 이동한 나라 개수 ArrayList<Pair> alist = new ArrayList<>(); //해당 점을 방문했을 때 이동한 점의 좌표 정보 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { q.add(new Pair(i, j)); while (!q.isEmpty()) { Pair p = q.poll(); if (!visited[p.x][p.y]) { visited[p.x][p.y] = true; cnt++; sum += map[p.x][p.y]; alist.add(new Pair(p.x, p.y)); for (int k = 0; k < 4; k++) { int nx = p.x + dx[k]; int ny = p.y + dy[k]; if (nx > 0 && nx <= n && ny > 0 && ny <= n && !visited[nx][ny] && checkPerson(map[p.x][p.y], map[nx][ny])) { q.add(new Pair(nx, ny)); } } } } //방문한 좌표가 인구 이동이 필요한 경우 if (alist.size() > 1) { int movingSum = sum / cnt; for (int k = 0; k < alist.size(); k++) { Pair p = alist.get(k); map[p.x][p.y] = movingSum; } hasMoreMoving = true; } //매 시작점마다 초기화 alist = new ArrayList<>(); sum = 0; cnt = 0; } } //end of for if (hasMoreMoving) { //더이상 움직일 게 있다면 visited배열 초기화 ans++; hasMoreMoving = false; visited = new boolean[n + 1][n + 1]; } else break; } System.out.println(ans); } //현재 인구와 이동할 인구의 차이 계산 public static boolean checkPerson(int curCnt, int nextCnt) { int absCnt = Math.abs(curCnt - nextCnt); if (absCnt >= min && absCnt <= max) return true; else return false; } public static class Pair { int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } } } | cs |
반응형
'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글
| [Algorithm] 백준/15685 :: 드래곤 커브 (0) | 2019.04.05 |
|---|---|
| [Algorithm] 백준/15686 :: 치킨 배달 (1) | 2019.03.27 |
| [Algorithm] 백준/13460 :: 구슬 탈출 2 (0) | 2019.03.10 |
| [Algorithm] 백준/16236 :: 아기 상어 (0) | 2019.03.10 |