https://goor.me/wDFSjuDNjzXTTqH4A

​

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
		for(int i =0; i <= N; i++){
			arr.add(new ArrayList<Integer>());
		}
		for(int i = 0; i < M; i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		boolean []visited = new boolean[N+1];
		
		for(int i = 0; i < arr.get(K).size(); i++){
			pq.add(arr.get(K).get(i));
		}
		
		visited[K] = true;
		int ans = K;
		int cnt = 1;
		while (!pq.isEmpty()){
			int node = pq.poll();
			if(visited[node] == false){
				ans = node;
				cnt++;
				visited[node] = true;
				pq = new PriorityQueue<Integer>();
				for(int i = 0; i < arr.get(node).size(); i++){
						pq.add(arr.get(node).get(i));
				}
			}
		}
		System.out.print(cnt);
		System.out.println(" " + ans);
	}
}

행렬 탐색 문제이다. 본인 또한 대부분 사람들과 비슷하게 그래프 탐색 원툴이기 때문에 그리디, dp같은건 잘 못푼다. 그래서 탐색 위주로 풀었다.

시작 노드로부터 인접 노드로 방문하는데

1. 한번 방문한 노드는 방문할 수 없고
2. 방문할 수 있는 노드중에 번호가 가장 작은 노드로 이동한다.

​

번호가 작은 노드로 이동한다는 규칙에서 우선 순위 큐 를 활용하는 아이디어를 바로 낼 수 있다.

물론 구름 측에서 제시한 코드를 보니 일반 큐에 넣은 후 정렬을 이용함. 아무거나 해도 상관 없을 것이다.

다만 우선순위 큐를 활용한다면, 매번 방문 후 다음에 방문할 노드를 큐에 넣을 때, 큐를 초기화해줘야 하는데, 이를 위해서 new를 사용하면 메모리 할당이 많아져 속도가 느려질 수도 있겠다. 근데 난 그냥 했다.

​

그리고 그래프에서 간선의 존재 유무를 굳이 확인할 필요가 없다면 인접행렬보단 인접 리스트로 구현하는 것이 공간 복잡도와 탐색 속도 면에서 낫기 때문에 arraylist를 이용한 인접 리스트를 선택한다.

https://goor.me/wDFSjuDNjzXTTqH4A

​

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Pair[][] arr = new Pair[n + 1][n + 1];
        for(int i=0; i<=n; i++){
            for(int j=0; j<=n; j++){
                arr[i][j] = new Pair();
            }
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            char c= st.nextToken().charAt(0);
            
            if(c == 'R'){
                for(int k=x;k<=n;k++)
                    arr[y][k].x += 1;
                
            } else if(c == 'L'){
                for(int k=1;k<=x;k++)
                    arr[y][k].x += 1;
                
            } else if(c == 'D'){
                for(int k=y;k<=n;k++)
                    arr[k][x].y += 1;
                
            } else if(c == 'U'){
                for(int k=1;k<=y;k++)
                    arr[k][x].y += 1;
             }
         }

         long ans=0;

         for(int i=1;i<=n;i++){
             for(int j=1;j<=n;j++){
                 ans+=arr[i][j].x*arr[i][j].y;
             } 
         }

         System.out.println(ans);
     }

     static class Pair{
         long y;
         long x;

         public Pair(){
             this.y=0;
             this.x=0;
          } 
      }
}

이 문제는 꽤 재밌었다.

탐색 + dp 문제

세로선 가로선이 교차하는 점의 개수를 구하면 되는데, 가로선끼리 세로선끼리는 겹치지 않는다.

그래서 2차원 배열로 맵을 만들고 각 칸마다 세로선과 가로선의 개수를 기록해준다.

이후에 세로선 개수 X 가로선 개수 를 누적합하면 정답이 나온다.

아까 공개된 정답 코드 봤는데 완벽하게 이해하지는 못했고 아마 비슷한 접근인 듯 한데, 정답 코드는 굳이 3차원 배열 써서 조건문 돌 때 마다 누적합까지 해줬고

나는 pair를 2차원 배열에 저장해서 세로선과 가로선을 기록했다.

​

이렇게 해서 네이버 페이 10000원을 벌었다.

https://goor.me/wDFSjuDNjzXTTqH4A

​

import java.io.*;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int [][]map = new int[N][N];
		int []ans = new int [32];
		
		Queue<Node> q = new LinkedList<>();
			
		int []dx = {-1, 1, 0, 0};
		int []dy = {0, 0, -1, 1};
		
		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 max = 0;
		int res = 0;
		
		for(int i = 0; i <N; i++){
			for(int j = 0; j < N; j++){
				int cnt = 0;
				if(map[i][j] != 0){
					cnt++;
					q.add(new Node(i, j));
					int num = map[i][j];
					map[i][j] = 0;
					while(!q.isEmpty()){
						Node node = q.poll();
						for(int k = 0; k <4; k++){
							int newi = node.i + dx[k];
							int newj = node.j + dy[k];
							if(newi >=0 && newi < N && newj >=0 && newj < N && map[newi][newj] == num){
								cnt++;
								q.add(new Node(newi, newj));
								map[newi][newj] = 0;
							}
						}
					}
					if (cnt >= K){
						ans[num] ++;
					}
				}
			}
		}
		for(int i =0; i<32; i++){
			if (ans[i] >= max){
				max = ans[i];
				res = i;
			}
		}
		System.out.println(res);
	}
}

class Node{
	int i;
	int j;
	
	Node(int i, int j){
		this.i = i;
		this.j = j;
	}
}

탐색 문제이다. bfs로 풀었다.

백준 10026 적록색약 문제와 유형이 비슷하다.

같은 정수가 상하 좌우로 k개 이상 인접해있다면 1개의 단지로 볼 수 있는데, 단지가 가장 많은 정수를 출력하면 된다.

​

같은 수가 3개 이상 인접해있다면 단지로 볼 수 있다면

​

1 1 1 2

2 2 1 3

1 1 3 3

​

이 예시에서는 1단지 1개 2단지 0개 3단지 1개 이다.

탐색을 통해 인접 행렬을 탐색하고 같은 수가 k개 이상 붙어있다면 단지의 수를 1개 늘려주면 된다.

주의해야할 점이 있다면 단지의 갯수만 따져야한다. 단지 + 숫자의 갯수까지 따지면 안된다.

예를 들어

​

1 1 1 1 1

1 1 1 1 3

1 1 1 3 3

3 3 3 1 1

​

이런 예시가 있다면 1단지 1개 3단지 2개로 3을 출력해야 한다. 1이 많다고 출력하면 안된다.

그리고 이거 리뷰 쓰면 네이버 포인트 5000원 준다.

https://goor.me/wDFSjuDNjzXTTqH4A

​

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
		for(int i =0; i <= N; i++){
			arr.add(new ArrayList<Integer>());
		}
		for(int i = 0; i < M; i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		Queue<Integer> q = new LinkedList<>();
		boolean []visited = new boolean[N+1];
		ArrayList<Node> ans = new ArrayList<>();
		
	
		for(int i = 0; i < N; i++){
			Double edge = 0.0;
			Node nd = new Node();
			if(arr.get(i).size() > 0 && !visited[i]){
				visited[i] = true;
				nd.nodeNum.add(i);
				for(int j = 0; j < arr.get(i).size(); j++){
					q.add(arr.get(i).get(j));
				}
				while (!q.isEmpty()){
					int nextNode = q.poll();
					edge++;
					if(!visited[nextNode]){
						visited[nextNode] = true;
						nd.nodeNum.add(nextNode);
						for(int j = 0; j < arr.get(nextNode).size(); j++){
							q.add(arr.get(nextNode).get(j));
						}
					}
				}
			nd.ans = edge / nd.nodeNum.size();
			ans.add(nd);
			}
		}
	
		for(int i = 0; i < ans.size(); i++)
			Collections.sort(ans.get(i).nodeNum);
		Collections.sort(ans, Node.customComparator);
		System.out.println(ans.get(0).ans);
		
		for(int i = 0; i <ans.get(0).nodeNum.size(); i++)
			System.out.print(ans.get(0).nodeNum.get(i) + " ");
	}
}


class Node{
    ArrayList<Integer> nodeNum = new ArrayList<>();
    Double ans;
	
    public static Comparator<Node> customComparator = new Comparator<Node>() {
        @Override
        public int compare(Node node1, Node node2) {
            // 1. ans가 가장 높은 것
            int ansComparison = Double.compare(node2.ans, node1.ans);
            if (ansComparison != 0) {
                return ansComparison;
            }

            // 2. ans가 같을 때 nodeNum의 인자갯수가 적은 것
            int numCountComparison = Integer.compare(node1.nodeNum.size(), node2.nodeNum.size());
            if (numCountComparison != 0) {
                return numCountComparison;
            }
					
            // 3. 2까지 같을 때는 nodeNum의 인자 중 가장 작은 인자가 있는 Node
            for (int i = 0; i < node1.nodeNum.size(); i++) {
                int numComparison = Integer.compare(node1.nodeNum.get(i), node2.nodeNum.get(i));
                if (numComparison != 0) {
                    return numComparison;
                }
            }

            return 0; // 모든 비교 기준이 같을 경우
        }
    };
}

쉽게 말하면 노드와 간선 수를 둘 다 구하면 된다.

근데 약간 꼼수 아닌 꼼수가 있다면, 실제는 양방향 간선으로 양 노드 간 간선 수를 하나로 세야 하지만,

그냥 각각 노드에서 간선의 수를 카운트 했기 때문에 2개로 치고 풀었다.

그래서 실제 밀도를 구하면 예시와는 다르지만 답은 맞는다.

그리고 밀도가 같을 때가 참 지저분한데, 그건 우리 형 gpt의 도움을 받아서 comparator의 compare 메소드를 오버라이드 해서 구현했다.

제시한 정답에서는 간선의 개수를 따로 세었는데. 난 그냥 탐색할 때 카운트 했다.