BOJ_G5_16234

📁 [G5_16234] 인구이동

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

public class Main {
	static int N, L, R;
	static int[][] map;
	static boolean[][] v;
	// 4방향 탐색 : 오, 밑, 왼, 위
	static int[] dx = { 1, 0, -1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	// 인구이동이 필요한 노드 리스트
	static ArrayList<Node> list;

	public static class Node{
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		// **** input start ****
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());

		// map 배열
		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());
			}
		}

		// **** input end ****

		// output
		System.out.println(move());

	}

	// 값 이동하기
	public static int move() {
		int res = 0;
		while(true) {
			// 인구이동을 나타내는 변수
			boolean isMove = false;
			v = new boolean[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					// 이미 방문했으면 통과
					if(v[i][j]) continue;

					int sum = bfs(i,j);
					// list가 1보다 크다면 인구이동
					if(list.size() > 1) {
						change(sum);
						isMove = true;
					}
				}
			}
			// 인구이동이 더이상 없으면 끝
			if(!isMove) return res;
			res++;
		}
	}

	// bfs
	public static int bfs(int x, int y) {
		Queue<Node> queue = new LinkedList<>();
		list =  new ArrayList<>();

		// 큐에 입력
		queue.offer(new Node(x, y));
		// 리스트에 입력
		list.add(new Node(x, y));
		// 방문처리
		v[x][y] = true;

		int sum = map[x][y];
		while(!queue.isEmpty()) {
			// 현재 노드 저장
			Node current = queue.poll();

			// 4방향 탐색
			int ny,nx;
			for(int i=0; i<4; i++) {
				nx = current.x + dx[i];
				ny = current.y + dy[i];

				// 범위를 벗어나거나 이미 방문했으면 통과
				if(nx < 0 || ny < 0 || nx > N-1 || ny > N-1 || v[nx][ny]) continue;

				// 인구수 차이 체크
				int temp = Math.abs(map[current.x][current.y] - map[nx][ny]);
				// 조건에 부합하면
				if(temp >= L && temp <= R) {
					// 입력하기
					queue.offer(new Node(nx,ny));
					list.add(new Node(nx,ny));
					// 값 더해주기
					sum += map[nx][ny];
					// 방문처리
					v[nx][ny] = true;
				}
			}
		}
		return sum;
	}

	// 인구 이동
	public static void change(int sum) {
		int avg = sum / list.size();
		for(Node n : list) {
			map[n.x][n.y] = avg;
		}
	}
}

🤔 나의 생각

처음에 문제를 보고 생각했던 방법이 전체 좌표를 돌면서 dfs와 4방향 탐색을 통해 연결조건이 되는 것들을 더하고 평균을 구해준 뒤 그 값들을 다른 배열에 저장해주자.
그리고 전체를 한 번 다돌고 그 다른 배열을 원래 map으로 copy하자 라고 생각을 했다.
이 과정들을 반복한 결과 제공된 tc는 다 맞았는데 숨겨진 tc에서 틀린 것이다.
생각을 해보니 기존 전체 좌표에서 하나의 연결그룹만 있으면 맞는데 여러개의 연결 그룹이 나올시 문제가 생기는 것이였다.

그래서 도움을 받아 새로 접근해 보았다.

• 전체 배열을 돌며 방문하지 않은 노드에 방문한다. 모든 노드를 방문할 때까지 반복
• BFS 알고리즘을 사용해서 노드를 방문한다.
• 방문한 노드들을 list에 넣어주고 합들을 저장한다.
• 전체 배열을 다 돌았으면 노드들의 인구이동을 시작한다. ( list의 크기가 1보다 커야 실행 - 연결된 것들이 존재한다는 뜻 )
• 인구 이동 코드에서 합들을 list 사이즈로 나눠서 모든 노드의 값을 변경시킨다.
• 위의 과정들을 반복해서 총 반복횟수를 구해준다.