[java]인구 이동 - 백준16234
문제
풀이
문제 해석을 하자면,
- 인구 이동이 불가능 할때까지 인구이동을 진행하고, 며칠 동안 발생하는지를 구하라.
- 하루에 어떻게 인구 이동을 하는지 문제에 나와있으므로 이를 참고하자.
풀이
- 두가지로 나눠서 풀었다.
- (1) 국경선을 OPEN 판단
- 2중 for문을 하고 방향 “오른쪽, 아래”만 확인하면 충분했다.
- 4가지 방향의 국경선과 인원 수를 Pair 객체에 담아서 사용했다.
- (2) 인구 이동
- dfs 를 모든 좌표에 적용했다.
- visited 를 활용하여 연합팀 만든것을 기록했다.
- 연합팀끼리도 구별을 해줘야 dfs 가 잘 동작하기 때문에 teamNumber 을 따로 부여했다.
- 인구 이동이 true 일때 계속 반복을 해야하기 때문에 “초기화”가 중요하다.
- init -> 연합 해체 + 모든 국경선 닫기 에 꼭 적용
- 마지막으로 기존에 “연합인원 계산”을 위해 따로 함수를 구현해서 사용했더니 “시간초과(80%)”가 떴었다.
- 해당 함수는 2*N^2 복잡도였고, 이를 while문 + 2중 for문과 중첩되니 복잡도가 2000*N^2 이 더 곱해져서 매우 커진게 문제였다고 판단된다.
- 이를 해결하기 위해 “연합인원 계산”을 “전역변수”를 활용해 dfs 함수에서 구해줘서 해결했다.
코드
public static int N, L, R;
public static int result;
public static Pair[][] inArr = new Pair[55][55];
public static int[][] visited = new int[55][55];
public static int[] dx = {0, 1, 0, -1}; // 오, 아, 왼, 위
public static int[] dy = {1, 0, -1, 0};
public static int team, teamMember;
public static void borderLineFun() {
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
for(int k=0; k<2; k++) { // 오른쪽, 아래만 체크하면 충분
Pair p = inArr[i][j];
int nx = i+dx[k];
int ny = j+dy[k];
if(nx<0||ny<0||nx>=N||ny>=N) continue;
int diff = Math.abs(inArr[i][j].people-inArr[nx][ny].people);
if(diff>=L && diff<=R) {
if(k==0) { // 오른쪽
inArr[i][j].r=1; inArr[nx][ny].l=1;
}else { // 아래
inArr[i][j].d=1; inArr[nx][ny].u=1;
}
}
}
}
}
//debug
// for(int i=0; i<N; i++) {
// for(int j=0; j<N; j++) {
// System.out.println("("+i+","+j+") "+inArr[i][j].r+" "+inArr[i][j].d+" "+inArr[i][j].l+" "+inArr[i][j].u);
// }
// }
}
public static void dfs(int cx, int cy, int teamNumber, List<Pair2> teamList) {
//base condition -> visited
//recursion
for(int i=0; i<4; i++) {
if(i==0) if(inArr[cx][cy].r==0) continue; // 국경선 체크 4개
if(i==1) if(inArr[cx][cy].d==0) continue;
if(i==2) if(inArr[cx][cy].l==0) continue;
if(i==3) if(inArr[cx][cy].u==0) continue;
// 이 아래는 국경선 열려있는 경우를 의미
int nx = cx + dx[i];
int ny = cy + dy[i];
if(nx<0||ny<0||nx>=N||ny>=N) continue;
if(visited[nx][ny] != 0) continue;
visited[nx][ny] = teamNumber; // 연합추가
team++; teamMember+=inArr[nx][ny].people;
teamList.add(new Pair2(nx, ny));
dfs(nx, ny, teamNumber, teamList);
}
}
public static void main(String[] args) throws IOException {
//init -> 백준 생략
//input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(stk.nextToken());
L = Integer.parseInt(stk.nextToken());
R = Integer.parseInt(stk.nextToken());
for(int i=0; i<N; i++) {
stk = new StringTokenizer(br.readLine(), " ");
for(int j=0; j<N; j++) {
int num = Integer.parseInt(stk.nextToken());
inArr[i][j] = new Pair(num);
}
}
//run
boolean moveCheck = true;
while(moveCheck) { // 인구이동 true면 계속 반복
// init -> 연합 해체 + 모든 국경선 닫기
moveCheck=false;
for(int i=0;i<N;i++) for(int j=0;j<N;j++) {
visited[i][j]=0;
inArr[i][j].r=0; inArr[i][j].d=0;
inArr[i][j].l=0; inArr[i][j].u=0;
}
//1. 국경선 OPEN
borderLineFun();
//2. 인구이동
int teamNumber = 1; // 연합팀 구별위해...!
for(int i=0; i<N; i++) {
for (int j = 0; j < N; j++) {
if(visited[i][j] != 0) continue;
visited[i][j] = teamNumber;
team=1; teamMember=inArr[i][j].people; // init
List<Pair2> teamList = new ArrayList<>(); // init
teamList.add(new Pair2(i, j));
dfs(i, j, teamNumber, teamList);
if(team>1) {
moveCheck=true;
int cal = teamMember / team; // 연합인원 계산
for(Pair2 p2 : teamList) {
inArr[p2.x][p2.y].people = cal; // update
}
}
teamNumber++;
}
}
if(moveCheck) result++;
}
//output
System.out.println(result);
}
static class Pair {
// r d l u -> 국경선 -> 기본값 0(=닫힘)
int people; int r; int d; int l; int u;
public Pair (int people) {
this.people=people;
}
}
static class Pair2 {
int x; int y;
public Pair2 (int x, int y) {
this.x=x; this.y=y;
}
}
느낀점
생략
댓글남기기