developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 통계학
  • MA모형
  • c++ 빌더 패턴
  • 삼성코테자바꿀팁
  • 삼성코테자바준비
  • 코테파이썬
  • AR모형
  • 백준파이썬풀이
  • SW역량테스트파이썬
  • Arima
  • 삼성코테구현풀이
  • 삼성코테파이썬
  • ARIMA모형
  • 삼성코테파이썬준비
  • 삼성코테준비
  • 삼성코테파이썬풀이
  • 시계열분석
  • 삼성코테구현문제추천
  • 삼성코테자바풀이
  • c++디자인패턴
  • SW역량테스트파이썬풀이
  • 카카오코테
  • 삼성코테기출자바풀이
  • 삼성코테기출
  • 운영체제인터럽트
  • 통계분석
  • 데이터분석
  • 시계열
  • 카카오코테java풀이
  • BOJ파이썬풀이

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen

인간 디버거의 로그 찍기

알고리즘/알고리즘문풀

BOJ - 인구 이동 16234번 (JAVA)

2022. 4. 29. 21:54

❓ 문제 - 백준 인구 이동 16234번 - JAVA 풀이법

출처 

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

 

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모

www.acmicpc.net

 

 

 

📝 문제해결법

1. 이 문제의 핵심은 그래프탐색(BFS)로 해결하는 것이다.

  • 두 개의 큐를 이용해 전체 나라를 탐색을 위한 queue와 국경선을 공유한 것의 지역을 담을 queue2를 통해 해결
  • 한 지역에 대해 국경선 공유할 때 연합인구수와 연합을 이루고 있는 국가 수를 저장하기 위해 cnt변수 이용
  • queue에 존재할 때까지 connet queue에 국경선을 공유하여 연합한 국가들의 위치를 append, 연합인구수(people)에 map[x][y] 를 더하고 연합을 이루고 있는 국가수(cnt)를 +1 증가시켜줌
  • 4방향을 돌면서 인접한 국가들과의 인구 수 차이(diff)를 계산하여 만약 diff가 주어진 L 이상 R 이하라면 국경선을 공유하기 위하여 visited로 방문 처리해주고, q에 국경선을 공유한 위치(nx, ny)를 append
  • 국경선이 공유되는지 queue를 통해서 다 확인 후에, 위에서 구한 두 번째 큐에서 국경선을 공유한 지역에  연합인구수 // 연합을 이루고 있는 개수로 graph 값을 변경시켜줌
  • bfs를 돌면서 count 즉, 국경선을 공유한 지역이 없다면 return 0
  • bfs를 돌면서 count 즉, 국경선을 공유한 지역이 있다면 return 1
  • 메인에서 while문 돌면서 국경선 공유 없을 때까지 인구이동 처리한다.

 

💻 소스코드

// BOJ - 인구이동(16234번)
// BFS

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

public class Main_16234 {
	public static int n, l, r;
	public static int[][] map;
	public static int[][] visited;
	public static class Node {
		int x;
		int y;
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	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 ans = 0;
		while(true) {
			boolean check = false;
			boolean[][] visited = new boolean[n][n];

			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(!visited[i][j]) {
						int change = bfs(visited, i, j);
						if(change >= 2) {
							check = true;
						}
					}
				}
			}
		
			if(!check) {
				break;
			}

			ans++;
			
		}
		
		System.out.println(ans);
	}
	
	public static int bfs(boolean[][] visited, int x, int y) {
		Queue<Node> q = new LinkedList<>();
		Queue<Node> q2 = new LinkedList<>();
		visited[x][y] = true;
		q.add(new Node(x, y));
		q2.add(new Node(x, y));
		
		int cnt = 1;
		int sum = map[x][y];
		while(!q.isEmpty()) {
			Node node = q.poll();
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];

				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					if(!visited[nx][ny]) {
						int diff = Math.abs(map[node.x][node.y] - map[nx][ny]);
						if(diff >= l && diff <= r) {
							cnt++;
							sum += map[nx][ny];
							visited[nx][ny] = true;
							q.add(new Node(nx, ny));
							q2.add(new Node(nx, ny));
						}
					}
				}
			}
		}

		if(cnt==1) {
			return 0;
		} 
		else {
			while(!q2.isEmpty()) {
				Node node = q2.poll();
				map[node.x][node.y] = sum / cnt;
			}
		}
		return cnt;
		
	}

}

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 미세먼지 안녕! 17144번 (JAVA)  (0) 2022.04.29
BOJ - 아기 상어 16236번 (JAVA)  (0) 2022.04.29
BOJ - 나무 재테크 16235번 (JAVA)  (0) 2022.04.22
BOJ - 큐빙 5373번 (JAVA)  (0) 2022.04.22
BOJ - 드래곤 커브 15685번 (JAVA)  (0) 2022.04.21
    '알고리즘/알고리즘문풀' 카테고리의 다른 글
    • BOJ - 미세먼지 안녕! 17144번 (JAVA)
    • BOJ - 아기 상어 16236번 (JAVA)
    • BOJ - 나무 재테크 16235번 (JAVA)
    • BOJ - 큐빙 5373번 (JAVA)
    developer-ellen
    developer-ellen

    티스토리툴바