인구 이동(BJ_G4_16234)

1. 문제 링크

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

16234번: 인구 이동

---

 

2. 나의 코드

메모리: 296944kb
시간: 676ms
코드 길이: 2333B
시간 복잡도 : O(N^4)
설명
- 0, 0부터 BFS 호출
- 마을이 형성되면 인구 이동 실시
- 방문하지 않은 모든 지점을 체크하면서 다른 마을이 있으면 위와 같은 로직 실행
- 인구 이동이 없으면 종료

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };
	static int N, L, R;
	static int[][] map;
	static boolean[][] visited;
	static List<Point> contryList;
	static boolean flag;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		map = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int result = 0;
		while (true) {
			flag = false;
			visited = new boolean[N][N];

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (!visited[i][j]) {
						bfs(new Point(i, j));
						move();
					}
				}
			}

			if (!flag) {
				System.out.println(result);
				break;
			}

			result++;
		}

	}

	// 인구 이동
	private static void move() {
		int population = 0;
		for (Point p : contryList) {
			population += map[p.x][p.y];
		}
		population = (int) population / contryList.size();
		for (Point p : contryList) {
			map[p.x][p.y] = population;
		}
	}

	public static void bfs(Point point) {
		Queue<Point> q = new LinkedList<Point>();
		contryList = new ArrayList<Point>(); // 연합 국가 리스트
		visited[point.x][point.y] = true;
		contryList.add(point);
		q.offer(point);

		while (!q.isEmpty()) {
			Point now = q.poll();

			for (int d = 0; d < 4; d++) {
				int nr = now.x + dr[d];
				int nc = now.y + dc[d];

				if (isValid(nr, nc) && !visited[nr][nc] && Math.abs(map[now.x][now.y] - map[nr][nc]) >= L
						&& Math.abs(map[now.x][now.y] - map[nr][nc]) <= R) {
					flag = true;
					visited[nr][nc] = true;
					Point np = new Point(nr, nc);
					contryList.add(np);
					q.offer(np);
				}
			}
		}
	}

	public static boolean isValid(int r, int c) {
		return 0 <= r && r < N && 0 <= c && c < N;
	}
}

 

---

 

3. 정답 코드

import java.util.*;
 
public class Main {
    
    static int n, l, r;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static ArrayList<Node> list; //인구 이동이 필요한 노드 리스트
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);    
 
        n = scan.nextInt();
        l = scan.nextInt();
        r = scan.nextInt();
        
        board = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = scan.nextInt();
            }
        }
        
        System.out.println(move());
    }
    
    public static int move() { //더 이상 인구이동이 일어나지 않을 때까지 반복
        int result = 0;
        while(true) {
            boolean isMove = false;
            visited = new boolean[n][n];
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    if(!visited[i][j]) {
                        int sum = bfs(i, j); //bfs탐색으로 열릴 수 있는 국경선 확인 하며 인구 이동할 총 인구수 반환
                        if(list.size() > 1) {
                            changePopulation(sum); //열린 국경선 내의 노드들 인구 변경
                            isMove = true;
                        }    
                    }
                }
            }
            if(!isMove) return result;;
            result++;
        }
    }
    
    public static int bfs(int x, int y) {
        Queue<Node> q = new LinkedList<>();
        list = new ArrayList<>();
        
        q.offer(new Node(x, y));
        list.add(new Node(x, y));
        visited[x][y] = true;
        
        int sum = board[x][y];
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            for(int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                if(nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny]) {
                    int diff = Math.abs(board[current.x][current.y] - board[nx][ny]);
                    if(l <= diff && diff <= r) {
                        q.offer(new Node(nx, ny));
                        list.add(new Node(nx, ny));
                        sum += board[nx][ny];
                        visited[nx][ny] = true;
                    }        
                }
            }
        }
        return sum;
    }
    
    public static void changePopulation(int sum) {
        int avg = sum / list.size();
        for(Node n : list) {
            board[n.x][n.y] = avg;
        }
    }
    
    public static class Node {
        int x; 
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

---

 

4. 배운 점

- 틀린 문제 다시 많이 풀어보자.