https://school.programmers.co.kr/learn/courses/30/lessons/49191
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
주석에 설명해 놓긴 했지만, 뭔가 그래프 문제보다 DP에 가까운 느낌이라고 해야되나
플로이드 워샬 같기도 하면서 살짝 다른거 같다.
로직 자체는 모든 정점을 방문하면서 확인한다는 부분은 비슷하지만, 결국 최단거리를 구하지도 않을 뿐더러
반복문 순서도 플로이드-워샬과 살짝 다르다.
플로이드 워샬은 k를 돌면서 점차 가장 짧은 걸 구해가지만, 이 문제는 그냥 i번째에는 i번째에 끝나서 뭔가 좀 다른 느낌이다.
그래서 포스팅 하는 것이기도 하다.(나름 재밌는 문제)
순위
import java.util.*;
/**
* 모든 정점을 다 접근해야 함
* 1 > 2, 2 > 3 ==> 1 > 3
* 1 < 2, 2 < 3 ==> 1 < 3
*
* 공통된 값은 고정으로 두고 나머지 노드 비교해야 함
*
* i k
* k j
*
* 1 1, 1 2, 1 3, 1 4, 1 5 에서 k가 5라고 가정하면
* 5 1, 5 2, 5 3, 5 4, 5 5 위 아래 비교
*
* graph[i][k] == graph[k][j] --> i > j
*/
class Solution {
public int solution(int n, int[][] results) {
int[][] graph = new int[n + 1][n + 1];
for(int[] result : results){
int a = result[0];
int b = result[1];
graph[a][b] = 1;
graph[b][a] = -1;
}
int answer = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= n; k++){
if(graph[i][k] == 1 && graph[i][k] == graph[k][j]){
graph[i][j] = 1;
graph[j][i] = -1;
} else if(graph[i][k] == -1 && graph[i][k] == graph[k][j]){
graph[i][j] = -1;
graph[j][i] = 1;
}
}
}
}
for(int i = 1; i <= n; i++){
int count = 0;
for(int j = 1; j <= n; j++){
if(graph[i][j] != 0){
count++;
}
}
if(count == n - 1){
answer++;
}
}
return answer;
}
}
'PS > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 두 큐 합 같게 만들기 - Java (0) | 2024.08.15 |
---|---|
[프로그래머스] 석유 시추 - Java (0) | 2024.08.15 |
[프로그래머스] 테이블 해시 함수 - Java (0) | 2024.07.04 |
[프로그래머스] 숫자 변환하기 - Java (0) | 2024.06.22 |
[프로그래머스] 도넛과 막대 그래프 - Java (1) | 2024.06.08 |