글 읽기 - 16234 인구이동 질문드립니다.

bbangssi91 5년 전 0

문제를 풀다가 생각을 미처하지 못한 부분이 있어서 질문드립니다.

코드 순서는 다음과 같습니다.

우선 문제에 필요한 조건을 입력받는다
isAvailable() 메소드는 인구 이동이 가능한지를 미리 검사합니다.

-> 인구이동이 하나라도 가능한 경우면 true를 리턴, 아니면 false를 리턴합니다.

3. 가능한 경우 BFS를 사용하여 L과 R 사이의 범위에 있는 경우에만 visited 배열을 true로 만들고 확장합니다.

4. 확장을 마치면(문을 전부 열었으면), 해당index의 배열에 sum/인구수 로 나누어서 배열을 갱신한다.

5. 다시 2번으로 돌아가서 true를 리턴하면 2->3->4 를 반복하고 false를 리턴하면 while 루프를 빠져나온다.

여기서 제가 질문드릴 부분은 2번에 해당하는 부분의 조건처리입니다.

다음 테스트케이스의 경우에서 제가 짠 코드의 예시는 다음과 같습니다.

49번 line의 for문에서 (0,0)부터 인덱스에서 확장을 하여
T T T
T T T
F T F 의 결과가 나왔습니다.

문제는 sum/인구수를 갱신하고 난 이후, 아직 for문이 전부 돌아간것이 아니기때문에
20 20 20
20 20 20
40 22 10 의 결과가 나오게 되고 (2,2) 에서 다시 확장을 하여

F F F
F F T
F F T 의 결과가 나오게됩니다.

결과적으로 while 루프는 1번만 돈것이 되기 때문에 결과 값 출력이 2가 나와야 하는데 1이 나오게 됩니다..
문제점이 무엇인진 알겠는데 코드를 어떻게 수정해야될지 도저히 감이 잡히질 않습니다
제가 짠 코드에서 어떻게 수정을 해야 문제를 개선할 수 있을까요ㅜㅜ 도움부탁드립니다

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Solution {

	static final int[] dy = {-1, 0, 1 , 0};
	static final int[] dx = {0, 1, 0, -1};
	static int result;
	static int N;
	static int L;
	static int R;
	static int map[][];
	static boolean moving[][];
	static boolean flag;
	
	static class Info{
		int row;
		int col;
		public Info(int row, int col) {
			this.row = row;
			this.col = col;
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		
		map = new int[N][N];
		moving = new boolean[N][N];
		
		//1. 입력받는다.
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				map[i][j] = sc.nextInt();
			}
		}
		
		//2. 먼저 검사를 한다.
		while(isAvailable(map)){
			flag = false;
			
			init();
			
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					//3. BFS를 해본다.
					BFS(i, j);
				}
			}
			
			if(flag) result += 1;
		}//end while
		
		
		System.out.println(result);
		
		sc.close();
	}//end main

	
	//2. 먼저 가능한지 검사를 한다.
	private static boolean isAvailable(int[][] copyMap) {
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				for(int dir = 0; dir < 4; dir++){
					int nextRow = i + dy[dir];
					int nextCol = j + dx[dir];
					
					if(nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= N) continue;
					
					int diff = Math.abs(copyMap[i][j] - copyMap[nextRow][nextCol]);
					
					if(diff >= L && diff <= R) return true;
				}
			}
		}
		
		return false;
	}//end isAvailable()

	//3. 가능한 경우면 BFS를 한다.
	private static void BFS(int curRow, int curCol) {
		boolean visited[][] = new boolean[N][N];
		Queue<Info> q = new LinkedList<>(); 
				
		q.add(new Info(curRow, curCol));
		visited[curRow][curCol] = true;
		
		while(!q.isEmpty()){
			Info i = q.poll();			
			
			for(int dir = 0; dir < 4; dir++){
				int nextRow = i.row + dy[dir];
				int nextCol = i.col + dx[dir];
				
				if(nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= N) continue;
				if(visited[nextRow][nextCol]) continue;
				
				
				int diff = Math.abs(map[nextRow][nextCol] - map[i.row][i.col]);
				
				if(diff >= L && diff <= R){ // 조건에 만족할 때만, 확장함.
					//System.out.println("map[" + curRow + "][" + curCol + "] - " + "map[" + nextRow + "][" + nextCol + "] = " + diff );
					visited[nextRow][nextCol] = true;
					q.add(new Info(nextRow, nextCol));
				}
			
			}//end for-dir
			
		}//end Queue-while
		
		movePop(visited);

	}//end BFS()

	//4. BFS한 결과를 바탕으로 갱신해준다.
	private static void movePop(boolean[][] visited) {
		int sum = 0;
		int divider = 0;
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(visited[i][j]){
					moving[i][j] = true;
					sum += map[i][j];
					divider += 1;
				}
			}
		}
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(visited[i][j] && moving[i][j]){
					map[i][j] = sum / divider;
				}
			}
		}
		
		if(divider > 1){
			flag = true;
		}
	}//end checkCount()
	
	private static void init() {
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				moving[i][j] = false;
			}
		}
	}//end init()


	
}//end class

exponential_e 5년 전 0

나라를 하나씩 옮겨가며 경계가 열리는지 검사를 하셨던데, 그렇게하려면 우선 나라가 하나 돌 때 마다 플래그 값을 초기화 해주고 그에 따른 결과 또한 한번씩 더해줘야 하는게 맞다는 생각입니다.

코드를 돌려본 결과 divider, 즉 경계가 열리는 나라의 갯수가 2개 이상인경우 플래그가 참이 되어야하는데,

플래그 값이 한번 참이 되니까 그 다음부턴 디바이더에 상관없이 계속 참의 값을 갖더라구요.

해당 입출력의 문제만 찾아보느라 맞는 코드인지는 사실 잘 모르겠습니다.

아래와 같이 고치시면 질문자님이 말씀하신 예제는 출력 2가 나옵니다.

        while(isAvailable(map)){			
			init();
			
			for(int i = 0; i < N; i++){
				for(int j = 0; j < N; j++){
					flag = false;
					BFS(i, j);
					if(flag) result += 1;
				}
			}
		}

bbangssi91 5년 전 0

음.. 답변자님께서 말씀하신 경우라면 while문 조건을 검사하기전에

for문 루프를 벗어나기전에 배열의 값이 갱신되어서, 불필요한 결과 값이 누적되는 문제가 발생할 거 같습니다 ㅠㅠ..

여튼 도움주셔서 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

16234 인구이동 질문드립니다.

bbangssi91 5년 전 0

exponential_e 5년 전 0

bbangssi91 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말