개발 블로그

문제 링크 : https://www.acmicpc.net/problem/1991

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

접근 방법

value를 pair로 지정해서 각각 first 는 leftChild로, second는 rightChild를 설정해준다.

그 후 전위, 중위, 후위 탐색 알고리즘에 맞게 unordered_map의 key와 value를 이용해준다. 

//
//  Tree_BOJ19991_트리순회.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/01.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
 
#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;
 
int N;
unordered_map<char, pair<char,char>> umap;
 
void preOrder(char c){
    if(umap.find(c) == umap.end()) return;
    else{
        cout << c;
        if(umap.find(umap[c].first) != umap.end() && umap[c].first != '.') preOrder(umap[c].first);
        if(umap.find(umap[c].second) != umap.end() && umap[c].second != '.') preOrder(umap[c].second);
    }
    
}
void inOrder(char c){
    if(umap.find(c) == umap.end()) return;
    else{
        if(umap.find(umap[c].first) != umap.end() && umap[c].first != '.') inOrder(umap[c].first);
        if(umap.find(umap[c].second) != umap.end() && umap[c].second != '.') inOrder(umap[c].second);
        cout << c;
 
    }
    
}
void postOrder(char c){
    if(umap.find(c) == umap.end()) return;
    else{
        if(umap.find(umap[c].first) != umap.end() && umap[c].first != '.') postOrder(umap[c].first);
        if(umap.find(umap[c].second) != umap.end() && umap[c].second != '.') postOrder(umap[c].second);
        cout << c;
 
    }
    
}
 
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> N;
 
    for(int i = 0; i<N; i++){
        char p, n1, n2;
        cin >> p >> n1 >> n2;
        umap[p] = make_pair(n1, n2);
    }
    
    preOrder('A');
    cout << "\n";
    inOrder('A');
    cout << "\n";
    postOrder('A');
 
    
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/7785

문제

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

접근 방법

map을 활용해서 key를 기준으로 정렬을 해준다. map을 선언할 때,

    map<string, string, greater<>> m; 

와 같이 선언해서 디폴트인 오름차순 정렬을 내림차순 정렬로 바꿔주면 된다.

그 후 마지막에 value가 "enter"인 사람의 이름만 출력해주면 사전순의 역순으로 출력된다.

//
//  Map_BOJ7785_회사에있는사람.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/06/30.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
 
#include <iostream>
#include <map>
using namespace std;
 
int main(){
    
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    map<string, string, greater<>> m;
    int n; cin >> n;
    for(int i = 0; i<n; i++){
        string name, EorL;
        
        cin >> name >> EorL;
        m[name] = EorL;
        
    }
    
    map<string, string>::iterator it;
    for(it = m.begin(); it!=m.end(); it++){
        if(it->second == "enter"){
            cout << it->first << "\n";
        }
    }
        
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/4195

문제

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

출력

친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

접근 방법

처음에는 unordered_map으로 풀었으나 시간 초과가 났다. 매 입력마다 value의 값을 변경하는 부분에서 시간이 많이 소요된 것 같다. 그래서 union and find 방법으로 해결하였다. (참고 : https://chanhuiseok.github.io/posts/baek-21/)

//
//  Map_BOj4195_친구네트워크.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/06/30.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
 
#include <iostream>
#include <unordered_map>
 
using namespace std;
 
int sizeArr[200000];
int parent[200000];
 
int getParent(int x){
    if(x==parent[x]) return x;
    else return parent[x] = getParent(parent[x]);
}
 
int main(){
    
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int test_case = 0;
    cin >> test_case;
    for(int t=1; t<=test_case; t++){
        
        unordered_map<string,int> umap;
        
        //F : 0~99,999 -> 친구 수 : 0 ~ 199,998 -> idx = 1~199,999 -> arr크기 = 200,000
 
        for(int i = 0; i<200000; i++){
            parent[i] = i;
            sizeArr[i] = 1;
        }
        
        int nodeNum = 0;
        
        int F; cin >> F;
        for(int i = 1; i<=F; i++){
            
            string name1, name2;
            cin >> name1 >> name2;
            
            if(umap.find(name1) == umap.end()){
                umap[name1]  = nodeNum++;
                
            }
            if(umap.find(name2) == umap.end()){
                umap[name2] = nodeNum++;
            }
            
            //find
            int n1 = umap[name1];
            int n2 = umap[name2];
            int p1 = getParent(n1);
            int p2 = getParent(n2);
            
            //union
            if(p1!=p2) {
                if(sizeArr[p1] < sizeArr[p2]) swap(p1, p2);
                sizeArr[p1] += sizeArr[p2];
                parent[p2] = p1;
            }
        
            cout << sizeArr[p1] << "\n";
            
        }
        
    }
    
    
    return 0;
}

(시간초과)

//
//  Map_BOj4195_친구네트워크.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/06/30.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
 
#include <iostream>
#include <unordered_map>
 
using namespace std;
 
 
int main(){
    
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int test_case = 0;
    cin >> test_case;
    for(int t=1; t<=test_case; t++){
        
        unordered_map<string,int> umap;
        
        int F; cin >> F;
        for(int i = 0; i<F; i++){
            string name1, name2;
            cin >> name1 >> name2;
            
            unordered_map<string, int> :: iterator it;
            
            if(umap.find(name1)==umap.end() && umap.find(name2)==umap.end()){   //둘다 없으면
                umap[name1] = 2;
                umap[name2] = 2;
                cout << umap[name2] << "\n";
            }
            else if(umap.find(name1) != umap.end() && umap.find(name2) == umap.end()){  //1만 있음
                int cnt = umap[name1];
                for(it = umap.begin(); it!=umap.end(); it++){
                    it->second = cnt + 1;
                }
                umap[name2] = cnt+1;
                
                cout << umap[name2] << "\n";
            }
            else if(umap.find(name1) == umap.end() && umap.find(name2) != umap.end()){  //2만 있음
                int cnt = umap[name2];
                for(it = umap.begin(); it!=umap.end(); it++){
                    it->second = cnt + 1;
                }
                umap[name1] = cnt + 1;
                
                cout << umap[name1] << "\n";
            }
            else{   //둘다 있음
                int cnt1 = umap[name1];
                int cnt2 = umap[name2];
                for(it=umap.begin(); it!= umap.end(); it++){
                    it->second = cnt1 + cnt2;
                }
                cout << umap[name1] << "\n";
            }
        }
        
    }
    
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/9375

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

접근 방법

unordered_map 을 이용해서 의상의 종류에 해당하는 옷 이름이 각각 몇개인지 구한다. 주어진 예시를 보면,

<headgear, 2>

<eyewear, 1>

라는 두개의 pair가 unordered_map에 저장이 된다. 

그 후, map 전체를 돌면서 second에 1을 더한 숫자를 곱해서 해빈이가 가진 옷들로 만들 수 있는 총 조합의 수를 구한다.

1을 더한 이유는 해당 옷을 입지 않는 경우도 있기 때문이다.

그리고 마지막에 1을 빼줘야하는데, 이유는 headgear도 입지 않고 eyewear도 입지 않는 경우(알몸인 상태)를 선택한 경우는 제외해야하기 때문이다. 

//
//  Map_BOJ9375_패션왕신해빈.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/06/27.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
 
#include <iostream>
#include <unordered_map>
 
using namespace std;
 
int main(){
    
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int test_case;
    cin >> test_case;
    for(int t = 0; t<test_case; t++){
       
        int n;
        cin >> n;
        int answer =  1;
        
        if(n==0) answer = 0;
        else{
            unordered_map<string, int> umap;
            
            for(int i = 0; i<n; i++){
                string name, type;
                cin >> name >> type;
                if(umap.find(type) != umap.end()){          //이미 맵에 해당 종류 있으면
                    int cnt = umap[type];   //value
                    umap[type] = cnt+1;                     //그 종류의 가짓수 1 증가
                }
                else{
                    umap[type] = 1;
                   // umap.insert(make_pair(type,1));         //없으면 1로 초기화해서 추가
                }
            }
           
            unordered_map<string,int>::iterator it;
            for(it = umap.begin(); it!=umap.end(); it++){
                answer *= (it->second) + 1;
            }
            answer -= 1;
        }
        
        cout << answer << "\n";
    
    }
    
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/1620

오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.

입력

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 포켓몬 이름의 최대 길이는 20이야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

접근 방법

unordered_map을 사용했다. (java - HashMap)

처음 포켓몬 이름을 입력 받을 때 strArr[]에도 같이 저장해준다. 번호로 포켓몬을 찾을 때 인덱스로 접근하기 위해서다.

그 후 이름을 입력했으면 map에서 찾을 수 있으므로 해당 이름(key)에 해당하는 value를 출력하면 되고, 

번호를 입력했으면 map에서 찾을 수 없으므로 strArr[번호]를 참조해서 출력한다. 

//
//  Map_BOJ1620_나는야포켓몬마스터이다솜.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/06/27.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
 
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
 
int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);	//없으면 시간 초과
    
    int N, M;
    cin>> N >> M;
    
    string strArr[100001];
    
    string name;
    unordered_map <string, int> pocketMon;
    for(int i = 1; i<=N; i++){
        cin >> name;
        
        pocketMon.insert(make_pair(name,i));
        strArr[i] = name;
    }
    
    for(int i = 0; i<M; i++){
        string input;
        cin >> input;
        if(pocketMon.find(input)!=pocketMon.end()){	//이름을 입력하면 map 참조
            cout << pocketMon.find(input)->second << "\n";
        }
        else{
            int num = stoi(input);			//번호를 입력한 경우에는 배열 참조
            cout << strArr[num] << "\n";
        }
    }
    
    return 0;
}

문제 링크 : https://www.acmicpc.net/problem/10816

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

접근 방법

이번에도 nextInt()와 System.out.print() 로 입출력을 하니까 시간초과가 나서 버퍼입출력으로 시간초과를 해결했다.

HashMap과 containsKey(), get() 메소드만 이용하면 쉽게 해결할 수 있다.

import java.util.*;
import java.io.*;
 
public class Map_BOJ10816_숫자카드2 {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer tokens;
	
	public static void main(String[] args) throws IOException {
		
		int N = Integer.parseInt(br.readLine());
		
		HashMap<Integer,Integer> map = new HashMap<>();
		
		tokens = new StringTokenizer(br.readLine());
		for(int i = 0; i<N; i++) {
			int num = Integer.parseInt(tokens.nextToken());
			if(!map.containsKey(num)) {
				map.put(num, 1);
			}
			else {
				int newValue = map.get(num) + 1;
				map.put(num, newValue);
			}
		}
		
		
		int M = Integer.parseInt(br.readLine());
		tokens = new StringTokenizer(br.readLine());
		for(int i = 0; i<M; i++) {
			int num = Integer.parseInt(tokens.nextToken());
			if(map.containsKey(num)) {
				bw.write(map.get(num) + " ");
			}
			else {
				bw.write("0 ");
			}
			
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

문제 링크 : https://www.acmicpc.net/problem/10815

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

접근 방법

로직은 간단하다. 상근이가 가지고 있는 N개의 카드를 오름차순으로 정렬한 뒤, M개의 정수를 하나씩 따져가면서 이분탐색을 진행하면 된다. 

@ 주의할 점

자바로 문제를 푸는 경우에 Scanner로 입력을 받으면 시간초과가 뜨는 것이다. BufferedReader, BufferedWriter로 시간을 단축하도록 하자!

import java.util.*;
import java.io.*;
public class BinarySearch_BOJ10815_숫자카드 {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		int[] arrN = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
 
		for(int i = 0; i<N; i++) {
			arrN[i] = Integer.parseInt(st.nextToken());
			//arrN[i] = sc.nextInt();
		}
		Arrays.sort(arrN);
		
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());		//여기서 다시 초기화 해줘야 함.
		for(int i = 0; i<M; i++) {
			
			int m = Integer.parseInt(st.nextToken());
			
			int first= 0;
			int last = N-1;
			boolean flag = false;
			while(first<=last) {
 
				int mid = (first+last)/2;
				int targetN = arrN[mid];
				 
				if(targetN==m) {
					flag = true;
					break;
				}
				
				if(targetN > m) {
					last = mid - 1;
				}
				else {
					first = mid + 1;
				}
				
			}
			if(flag) bw.write(1 + " ");
			else bw.write(0 + " ");
			
		}
	bw.flush();
	bw.close();
	br.close();
	}
}

문제 링크 : https://www.acmicpc.net/problem/16234

문제

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

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

접근 방법

각 땅 (r,c) 에 대해 무한루프를 돌면서 

     - BFS를 이용해 국경선을 서로 열 수 있는 땅을 Queue에 다 넣고, BFS 탐색이 끝나면 인구이동을 해준다. 

     - 모든 칸에 대해 인구이동 여부를 탐색 했으면 다시 처음으로 돌아가서 visited를 초기화 시킨 후 재 탐색한다. (만약 이 단계에서 탐색이 끝났을 때 인구이동이 한 번도 발생하지 않았다면 무한루프를 종료시킨다.)

import java.util.*;
 
class Pair16234{
	Integer r, c;
	public Pair16234(Integer _r, Integer _c) {
		this.r = _r;
		this.c = _c;
	}
	public int getRow() {
		return this.r;
	}
	public int getCol() {
		return this.c;
	}
	
}
public class SM_BOJ16234_인구이동 {
 
	static int N, L, R, answer;
	static int[][] map, visited; 
	static int[] dr,dc;
 
	static boolean chk(int a, int b) {
		int sub = Math.abs(a-b);
		if(L <= sub && sub <=R) return true;
		else return false;
	}
	
	static boolean BFS(int r, int c) {
		
		Queue<Pair16234> que = new LinkedList<Pair16234>();
		ArrayList<Pair16234> vec = new ArrayList<Pair16234>();
		int sum = 0;
		
		Pair16234 p = new Pair16234(r,c);
		que.add(p);
		vec.add(p);
		sum = map[r][c];
		
		while(!que.isEmpty()) {
			Pair16234 pair = que.poll();
			int cr = pair.getRow();
			int cc = pair.getCol();
			
			visited[cr][cc] = 1;
			
			for(int i = 0; i<4; i++) {
				int nr = cr + dr[i];
				int nc = cc + dc[i];
				if(nr<1 || nr>N || nc<1 || nc>N || visited[nr][nc]==1) continue;
				
				if(chk(map[cr][cc], map[nr][nc])) {
					visited[nr][nc] = 1;
					Pair16234 p_next = new Pair16234(nr,nc);
					que.add(p_next);
					vec.add(p_next);
					sum += map[nr][nc];
				}
			}
		}
		
		if(vec.size()==1) {
			visited[vec.get(0).getRow()][vec.get(0).getCol()] = 0;
			return false;
		}
		else {
			int avg = sum / vec.size();
			for(int i = 0; i<vec.size(); i++) {
				int row = vec.get(i).getRow();
				int col = vec.get(i).getCol();
				map[row][col] = avg;
			}
			return true;
		}
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
 
		Scanner sc = new Scanner(System.in);
		dr = new int[4];
		dc = new int[4];
		dr[0] = -1; dr[1] = 0; dr[2] = 1; dr[3] = 0;
		dc[0] = 0; dc[1] = 1; dc[2] = 0; dc[3] = -1;
 
		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		
		map = new int[51][51];
		visited = new int[51][51];
		for(int i = 1; i<=N; i++) {
			for(int j = 1; j<=N; j++) {
				map[i][j] = sc.nextInt();
				visited[i][j] = 0;
			}
		}
		
		answer = 0;
 
		int cnt = 0;	
		while(true) {
			
			if(cnt==N*N) break;
			cnt = 0;
			
			boolean flag = false;
			
            //인구 이동 끝나고 초기화 
			for(int r = 1; r<=N; r++) {
				for(int c = 1; c<=N; c++) {
					visited[r][c] = 0;
				}
			}
			
			for(int i = 1; i<=N; i++) {
				for(int j = 1; j<=N; j++) {
 
					if(visited[i][j]==0) {
						boolean res = BFS(i,j);		//국경선 열렸으면 true 
						if(res) {
							flag = true;
						}					
						else cnt++;
					}
				}
			}
			
			if(flag) answer++;
		}
		System.out.println(answer);
	}
 
}