[백준] 2458 키 순서

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

학생의 키를 비교하기 위하여 DFS, BFS, 다익스트라 탐색을 고려하였으나, 학생들간 비교 정보에 대해서 모든 학생들을 기준으로 확인해야 했으므로 여러번 탐색이 필요하였습니다.

이러한 경우 제한 시간 문제가 발생하였습니다.

 

이후 플로이드 워셜을 고려하였으며, 처음에는 현재 학생보다 키가 큰 경우에는 배열의 값을 1, 작은 학생의 경우 -1 의 가중치를 주었습니다. 이후 판별에서는 탐색하는 학생과 같은 레벨에 있는 학생이 있는지 여부로 판별하려 하였으나, 예외 사항이 발생하였습니다.

가중치를 1과 -1로 주게 되어 같은 레벨에 존재하지 않지만, 키를 비교할 수 없는 경우가 발생하였습니다.

 

이러한 문제를 해결하기 위하여 -1 의 가중치를 제거하고, 학생보다 키가 큰 경우만 고려하였습니다.

그래서 한 학생보다 얼마나 키 차이가 나는지는 중요하지 않고, 키가 큰지와 작은지만 구분하였습니다.

2) 알고리즘

• 플로이드 워셜

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N, M = map(int, sys.stdin.readline().split())                       # 학생의 수, 학생 비교 횟수
distance = [[0] * N for _ in range(N)]                              # 학생들 키 비교 배열
answer = 0                                  

for _ in range(M):
    short, tall = map(int, sys.stdin.readline().split())            # 키 비교한 정보를 2차원 배열에 기록
    distance[short-1][tall-1] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if distance[i][k] == 1 and distance[k][j] == 1:         # i 보다 k 가 크고, k 보다 j 가 크면
                distance[i][j] = 1                                  # i 보다 j 가 크다

for i in range(N):
    cnt = sum(distance[i])                          # 현재 학생보다 키가 큰 학생의 수
    for j in range(N):                              # 현재 학생보다 키가 작은 학생의 수
        cnt += distance[j][i]
    if cnt == N-1:                                  # 키 크거나 작은 학생들이 모두 있을때 정답 케이스 1 증가
        answer += 1

print(answer)

 

잘못된 코드

import sys
sys.stdin = open('input.txt')

N, M = map(int, sys.stdin.readline().split())                       # 학생의 수, 학생 비교 횟수
distance = [[1e10] * N for _ in range(N)]                              # 학생들 키 비교 배열
answer = 0

for _ in range(M):
    short, tall = map(int, sys.stdin.readline().split())
    distance[short-1][tall-1] = 1									# 키가 큰 학생
    distance[tall-1][short-1] = -1									# 키가 작은 학생

for k in range(N):
    for i in range(N):
        for j in range(N):
    		# 키 연결 관계가 있을때
            if (distance[i][k] != 1e10 and distance[k][j] != 1e10) and distance[i][j] == 1e10:
                distance[i][j] = distance[i][k] + distance[k][j]

pprint(distance)

# 정답 판별 불가능

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2458

2458번: 키 순서

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다