[파이썬, Java] 2458. 키 순서

문제

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 

• 1번 학생의 키 < 5번 학생의 키
• 3번 학생의 키 < 4번 학생의 키
• 5번 학생의 키 < 4번 학생의 키
• 4번 학생의 키 < 2번 학생의 키
• 4번 학생의 키 < 6번 학생의 키
• 5번 학생의 키 < 2번 학생의 키

이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다. 

1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다. 

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다. 

출력

자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다. 

예제 입력 1 

6 6

1 5

3 4

5 4

4 2

4 6

5 2

예제 출력 1 

1

예제 입력 2 

6 7

1 3

1 5

3 4

5 4

4 2

4 6

5 2

예제 출력 2 

2

예제 입력 3 

6 3

1 2

2 3

4 5

예제 출력 3 

0

 

 

👻 나의 풀이

import sys
from collections import defaultdict, deque
input=sys.stdin.readline
N, M=map(int, input().split())      # 학생들의 수, 두 학생 키를 비교한 횟수
dic=defaultdict(set)
for m in range(M) :
    a, b=map(int, input().split())      # 번호 a < 번호 b
    dic[a].add(b)

def bfs(start) :
    que=deque([start])
    visit=[0]*(N+1)
    visit[start] = 1
    while que :
        num=que.popleft()
        for i in dic[num] :
            if not visit[i] :
                visit[i]=1
                dic[start].add(i)
                que.append(i)

for i in range(1, N+1):
    bfs(i)

def cnt(n) :
    cnt=0
    for k, v in dic.items() :
        if n in dic[k] :
            cnt+=1
    return cnt

print(len([k for k in dic if len(dic[k])+cnt(k) == N-1]))

bfs, 해시

start번호를 이긴 dic[start]가 진 번호에도 진다.

cnt 함수는 n이 이긴 횟수를 센다.

k가 진 횟수+k가 이긴 횟수 == N-1이면 자신의 키가 몇 번째인지 알 수 있다.

 

 

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());     // 두 학생 키를 비교한 횟수
        HashMap<Integer, ArrayList<Integer>> map=new HashMap<>();
        int[] cnt=new int[N+1];
        int ans=0;
        
        for(int i=0; i<M; i++){
            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());     // 번호가 a인 학생이 번호가 b인 학생보다 키가 작음
            int b=Integer.parseInt(st.nextToken());
            ArrayList<Integer> tmp=new ArrayList<>();
            if(!map.containsKey(a)){
                tmp.add(b);
            }else{
                tmp=map.get(a);
                tmp.add(b);
            }
            map.put(a, tmp);
        }

        for(int i=1; i<=N; i++){
            Deque<Integer> deque=new LinkedList<>();
            boolean[] visit=new boolean[N+1];
            deque.add(i);
            visit[i]=true;
            while(!deque.isEmpty()){
                int num=deque.pollFirst();
                if(i != num){
                    cnt[i]+=1;
                    cnt[num]+=1;
                }
                if(!map.containsKey(num)) continue;
                for(int key : map.get(num)){
                    if(!visit[key]){
                        visit[key]=true;
                        deque.add(key);
                    }
                }
            }
        }

        for(int i=1; i<=N; i++){
            if(cnt[i] == N-1){
                ans++;
            }
        }
        System.out.println(ans);
    }
}

다른 사람의 파이썬 풀이에서 배운 내용을 자바로 구현했다.

1부터 N까지 deque에 넣으면서 bfs 탐색을 한다.

deque에서 뺀 원소 num과 시작원소 i가 다르면 배열 cnt의 i, num 인덱스 값을 1 증가시킨다.

num과 i의 사이의 승부 여부를 알고 있기 때문에

 

 

🐩 다른 사람 풀이

# https://donghak-dev.tistory.com/169?category=904697
from collections import defaultdict, deque

N, M=map(int, input().split())

order_h=defaultdict(list)
order_l=defaultdict(list)
degree=[0]*(N+1)
for _ in range(M) :
    Low, High=map(int, input().split())
    order_h[Low].append(High)
    order_l[High].append(Low)

for key in order_h.keys() :
    visited=[0]*(N+1)
    Q=deque()
    Q.append(key)
    visited[key]=1

    while Q :
        now=Q.popleft()
        if now not in order_h.keys() :
            continue
        for element in order_h[now] :
            if visited[element] == 0 :
                visited[element]=1
                degree[element]+=1
                Q.append(element)

for key in order_l.keys() :
    visited=[0]*(N+1)
    Q=deque()
    Q.append(key)
    visited[key]=1

    while Q :
        now=Q.popleft()
        if now not in order_l.keys() :
            continue
        for element in order_l[now] :
            if visited[element] == 0 :
                visited[element]=1
                degree[element]+=1
                Q.append(element)

print(degree.count(N-1))

딕셔너리가 2개다.

order_h는 키보다 작은 값, order_ㅣ은 키보다 큰 값을 담는 딕셔너리다.

for문 2번 쓰기 보다는 함수를 만들어서 두번 호출했으면 좋았을 것 같다.

for문 안에 코드는 똑같으니까

 

 

import sys
from collections import defaultdict, deque

N, M=map(int, sys.stdin.readline().split())      # 학생들의 수, 두 학생 키를 비교한 횟수
graph=[[] for _ in range(N+1)]
cnt=[1]*(N+1)
q=deque([])

for _ in range(M) :
    a, b=map(int, sys.stdin.readline().split())
    graph[a].append(b)

for i in range(1, N+1) :
    visited=[False]*(N+1)
    q.append(i)
    visited[i]=True
    
    while q :
        j=q.popleft()
        if i != j :
            cnt[i]+=1
            cnt[j]+=1
        for k in graph[j] :
            if not visited[k] :
                visited[k]=True
                q.append(k)
                
sys.stdout.write(str(cnt.count(N)))

bfs

이전 풀이와 다른점은 bfs를 한 번만 탐색하고 i와 j가 다르면 동시에 1을 증가시킨다.

되게 효율적이다.

 

 

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

class Main{
    static int N, M;
    static int[][] adj;
    static boolean[] visit;

    public static void main(final String[] args) throws NumberFormatException, IOException{
        final BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());

        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());

        adj=new int[N+1][N+1];
        visit=new boolean[N+1];

        for(int i=0; i<M; i++){
            st=new StringTokenizer(br.readLine());

            final int v1=Integer.parseInt(st.nextToken());
            final int v2=Integer.parseInt(st.nextToken());

            adj[v1][v2]=1;
        }

        for(int i=1; i<=N; i++){
            if(visit[i])
                continue;
            dfs(i);
        }

        int answer=0;

        for(int i=1; i<=N; i++){
            int curSum=0;
            for(int j=1; j<=N; j++){
                curSum+=adj[i][j]+adj[j][i];
            }
            if(curSum == N-1)
                answer++;
        }

        System.out.println(answer);
    }

    public static void dfs(final int s){
        if(visit[s])
            return;

        for(int i=1; i<=N; i++){
            if(adj[s][i] == 1){
                dfs(i);
                for(int j=1; j<=N; j++){
                    adj[s][j]=adj[s][j] | adj[i][j];
                }
            }
        }

        visit[s]=true;
    }
}

DFS

adj[v1][v2]=1는 v1이 v2보다 작은 것이다.

s와 연결된 i의 연결정보를 알아내기 위해 재귀호출한다.

 

 

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

class Main{
    static int N, M;
    static int[][] map;

    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st=new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());

        map=new int[N+1][N+1];

        for(int i=0; i<M; i++){
            st=new StringTokenizer(br.readLine());

            int s=Integer.parseInt(st.nextToken());
            int c=Integer.parseInt(st.nextToken());

            map[s][c]=1;    // 단방향
        }

        // 인접행렬에서 사용하지 않는 0번 칸을 플래그 변수로 활용
        for(int i=0; i<map.length; i++){
            map[i][0]=-1;
        }

        int totalN=0;   // 순서를 정확히 알게되는 학생의 수

        for(int i=1; i<=N; i++){
            dfs(i);     // 순회
        }

        // 나보다 키가 작은아이들, 큰아이들의 합을 구해서 N-1이면 순서를 정확하게 알 수 있는 사람
        for(int i=1; i<map.length; i++){
            for(int j=1; j<map.length; j++){
                map[0][i]+=map[j][i];       // 정점 i로 진입하는 정점들의 개수를 저장
            }
        }
        for(int i=1; i<map.length; i++){
            if(map[0][i]+map[i][0] == N-1){
                totalN++;
            }
        }

        System.out.println(totalN);
    }

    public static void dfs(int v){
        if(map[v][0] != -1){    // 정점 v에 대해서 부모를 체크해 둔 상태면
            return;
        }
        // 현재 v정점의 부모가 누구인지를 인접행렬에 저장
        for(int i=1; i<map.length; i++){
            if(map[v][i] == 1){
                dfs(i);
                for(int j=1; j<map.length; j++){
                    map[v][j]=map[v][j] | map[i][j];
                }
            }
        }

        // 인접행렬의 0번째 칸은 v정점의 부모의 개수 몇개인지 저장해놓기
        int sum=0;
        for(int i=1; i<map.length; i++){
            sum+=map[v][i];     // 인접한 부모는 1이고 안했으면 0
        }
        map[v][0]=sum;      // 안쓰는 0번째 인덱스에 부모의 개수인 sum 값 저장
    }
}

DFS

이전 풀이와 방법이 같다.

 

 

문제 출처 👉 백준