[10주차_수요일] 역사

[yeahdy]

• 사이트 : 백준(BOJ)
• 문제: 역사
• 번호: 1613
• 레벨: 골드3

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[yeongleej]

🤔 시간복잡도 고려사항

• 사건의 개수: n <= 400
• 전후관계: k<=50000
• 알고 싶은 사건 수: s <=50000

=> 노드들의 최단거리를 구해야 함 => n이 충분히 작으므로 모든 노드에서 다른 모든 노드까지의 최단거리를 구할 수 있는 플로이드와샬 활용 => O(n^3)

💡 풀이 아이디어

• 플로이드 와샬 활용
  • 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
  • a에서 b로가는 경로에서 특정한 노드 k를 거쳐 가는 경우를 확인
  • Dab = min(Dab, Dak + Dkb)
  • *자신으로 가는 비용은 0으로 초기화
• a -> b로 가는 비용이 INF가 아니면 -1
• b -> a로 가는 비용이 INF가 아니면 1
• a -> b로 가는 비용이 INF라면 0

[KodaHye]

🤔 시간복잡도 고려사항

• n: 사건의 개수 <= 400
• k: 사건의 전후 관계의 개수 <= 50,000
• s: 관계를 알고 싶은 사건 쌍의 수 <= 50,000
• 그래프로 문제 풀이: O(k (n + k)) = 50,000 50,400
• 배열로 문제 풀이: O(n n n) = 64,000,000

💡 풀이 아이디어

• 모든 지점 간의 선후 관계를 구해야 되는 문제 → 플로이드 워셜을 통해 모든 경우를 구해줌!
  • 한 지점에서 다른 지점을 갈 수 없다면, 어떤지 모르는 경우: 0
  • 한 지점에서 다른 지점을 갈 수 있다면, 사건이 먼저 일어난 경우: -1
  • 그 반대 지점은 시작 지점 기준으로 했을 때, 나중에 일어난 경우이기 때문에1이 됨

자기 자신으로 가는 길을 0으로 초기화하는 부분을 까먹었네요,,, !!!,,, (이 부분 잊지 말좌,,,)

[Jewan1120]

🤔 시간복잡도 고려사항

• 사건의 개수 n(400 이하의 자연수)
• 플로이드 와샬의 O(N^3) 가능

💡 풀이 아이디어

• 현재 노드를 다른 노드를 참고하여 값 결정하기 → 플로이드 와샬
• 상태를 이용한 노드의 상대적인 위치를 결정
  • -1: 앞섬, 0: 알 수 없음, 1: 뒤짐
• i → j를 결정하기 위해서 i → p의 상태와 p → j의 상태를 이용해서 결정
  • i → p와 p → j가 동일하다면 i → j도 동일한 상태를 가짐

[baexxbin]

🤔 시간복잡도 고려사항

• 사건의 개수: n <= 400
• 플로이드 와샬 O(N^3)가능

💡 풀이 아이디어

• 플로이드 와샬을 통해 i → j로 가는 경로 판단
• 구해진 order[i][j]값은 i, j간의 선후관계를 나타냄
  • order[i][j]값이 INF라면 경로가 없어 모름 (0)
  • order[i][j]값이 INF가 아니라면 경로가 있는 것으로 선후 관계 판단 가능 (i → j (-1), j → i(1))

플로이드 와샬이 모든 지점 간의 선후 관계를 구할 수 있는진 오늘 처음 알았네요...!! 와샬이 구현 방법말고 개념도 더 공부해야겠습니당

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 플로이드 와샬
• 시간복잡도: n(400 이하의 자연수) s(50,000 이하의 자연수) 플로이드 와샬로 풀이 시 O(n^3) > 10^6

💡 풀이 아이디어

• graph[먼저 일어난 사건][나중에 일어난 사건] = true 그래프 모델링하기
  • graph[to][from] 으로 사건 간 전후관계를 연결 짓기
• 플로이드 와샬 알고리즘을 통해 경유지 찾기
  • graph[to][k] && graph[k][from]
  • 중간거점을 기준으로 전후관계 사이에 다른 사건과 전후 관계 연결이 가능한 사건이 있는지 탐색
• 사건의 전후관계 찾기
  • graph[사건1][사건2] 또는 graph[사건2][사건1] 넣으면서 경유가 가능하다면 -1 또는 1 출력
  • 경유가 불가하다면 0 출력

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : O(N^3)
  • 40^3 < 1초

💡 풀이 아이디어

구하는 것 : 일부 사건의 전후 관계를 파악(-1, 0, 1)

• 플로이드-와샬 사용 이유
  1. 사건 들의 전후 관계(경로)가 주어짐 → 모든 정점에 대한 경로를 알고 있음
  2. 주어진 사건들 중 일부 사건의 전후 관계를 파악
• 문제에서 사건의 전후 관계만 알려줘서 방문 여부만 확인 -> boolean[][] visited
• 전후 관계를 입력 받은 것들은 true처리
• 문제 요구 사항에 맞게 출력 : -1, 0, 1

  전후 관계 입력받는 반복문을 N까지 입력 받아서 런타임 오류 에러 발생했었습니다,,ㅎ 문제 조건 잘 보기!