uzzam
uzzam.dev
uzzam
전체 방문자
819
오늘
4
어제
14
  • 분류 전체보기 (29)
    • 프로젝트 (4)
      • 담타 (4)
    • CS (0)
      • 운영체제 (0)
    • ps, cp (4)
      • 코딩테스트 cheatsheet (3)
      • baekjoon (1)
      • codeforces (0)
    • languages (0)
      • dart (0)
    • frameworks (2)
      • flutter (2)
    • ios (1)
    • 블로그 (10)
    • git (2)
    • blockchain (0)
    • etc. (6)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

  • Apple Silicon(M1) 맥북 공장 초기화하기
    2022.12.07
  • 군대 사지방에서 개발하는 방법들
    2022.12.07
  • netlify 로 gatsby 블로그 자동배포하기
    2022.12.07
  • porkbun에서 깃허브 블로그 도메인 구매하기 및 도메인⋯
    2022.12.07
    porkbun에서 깃허브 블로그 도메인 구매하기 및 도메인⋯
  • 빠르게 Gatsby + Github pages 로 블로그 ⋯
    2022.12.07

태그

  • 블로그

최근 댓글

  • 블로그 글 잘 쓰시네요 ㅎㅎ 잘 보구 갑니당
    alpha-traveler
  • 마침 찾아보던 글인데 글 올려주셔서 감사합니다 ㅎㅎ
    alpha-traveler

최근 글

  • 내 인생 최고의 책
    2023.01.10
    내 인생 최고의 책
  • 새해는 특별하니까
    2023.01.08
    새해는 특별하니까
  • 안드로이드 splash screen 중복 문제 해결하기
    2023.01.07
  • git clean -fdx 하고 잠못자기
    2023.01.06
  • Xcode developer mode disabled 해결⋯
    2023.01.05

티스토리

hELLO · Designed By 정상우.
uzzam

uzzam.dev

ps, cp/baekjoon

[baekjoon] 2278 - 그래프 복원

2022. 12. 10. 05:44

문제 링크 : https://www.acmicpc.net/problem/2278

 

2278번: 그래프 복원

첫째 줄에 그래프를 복원할 수 있으면 1을, 없으면 0을 출력한다. 복원할 수 있을 때, 다음 m개의 줄에 각 간선을 a, b, c의 형태로 출력한다. 이는 정점 a, b를 연결하는 가중치 c인 간선이 있다는 의

www.acmicpc.net

시도한 사람, 푼 사람이 거의 없다.. 

평소에 해설을 쉽게 보는 편인데 해설이 없어서 강제로 열심히 풀었다.

백준 문제풀이는 너무 많은 사람이 올려서 쓰지 않을 생각이었지만 혹시 궁금한 사람이 있을 수 있으니..


문제유형 - 그래프 복원

비슷한 문제는 1507번 - 궁금한 민호(https://www.acmicpc.net/problem/1507)가 있다.

두 문제의 핵심은 그래프를 복원하는 것.

플로이드 워셜 알고리즘을 통해 최단거리가 정해진 그래프를 원래 그래프로 복원하라는 문제 유형이다.

 

플로이드 워셜에서 핵심은

graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) 이다.

 

즉 a -> k -> b 경로가 더 짧을 경우에만 graph[a][b]를 갱신시켜준다.

 

반대로 생각해보면 graph[a][b] 가 graph[a][k] + graph[k][b] 와 같다면 갱신되었다는 것을 알 수 있다.

그리고 짧은 경우에만 갱신되므로 a -> b / a -> k -> b 중 후자가 최단거리라는 것이다. 

그럼 도로를 최소한만 쓰기위해서는 a -> b 의 경로는 필요없다.

이를 각자의 방법으로 표시해주면 된다.

 

만약 graph[a][b] > graph[a][k] + graph[k][b] 라면 말이 되지 않는다. 

플로이드 워셜이 적용되었다면 해당 결과는 나올 수 없다.

 

만약 graph[a][b] < graph[a][k] + graph[k][b] 라면 a -> k -> b 경로가 있기는 하지만 최단 경로는 아니라는 것이다.

 

주의 : a == k 이거나 b == k 이면 바로 가는 선분을 뜻하므로 제외시켜야 한다.


해설

입력값으로 주어진 그래프를 그릴 수 있는 최소한의 선을 확정짓고 나머지는 아무거나 채우라는 좀 허접한? 문제이다.

두 정점 사이의 최단거리는 500보다 작거나 같은 자연수이므로 최단거리가 아닌 것은 500으로 전부 채우면 된다.

이 때 필요한 간선의 개수는 M 이고 N 개의 정점을 가진 그래프에서 그릴 수 있는 간선의 최대 개수는 N (N - 1) // 2 이다.

 

아래 세 가지 경우는 말이 안되어 0을 출력해야 한다

- 무조건 있어야 하는 선의 개수가 M 보다 큰 경우

- 필요한 간선의 개수까지 그려하는 선의 개수(M - 무조건 있어야하는 선의 개수)가 그릴 수 있는 최대의 수(간선의 최대 개수 - 무조건 있어야 하는 선의 개수)가 보다 큰 경우 == 즉  M > 간선의 최대 개수 == M > N(N - 1) // 2

- 또 그래프를 복원하는 과정에서 말이 안되는 경우 (graph[a][b] > graph[a][k] + graph[k][b] 인 경우)

 

이 외의 경우 가능한데, 이후 점들을 돌면서 선분이 꼭 그려져 있는 경우 해당 선분을 출력하고, 선분이 없는 부분은 개수를 세어가며 출력해주면 된다.


추가 테스트케이스

더보기

입력

4 6 
1 1 2
2 1
1

 

출력

1
1 2 1
1 3 1
1 4 500
2 3 500
2 4 1
3 4 1


입력 

4 5
1 1 2
2 1
1

 

출력
1
1 2 1
1 3 1
1 4 500
2 4 1
3 4 1


입력

5 10
3 3 13 8
6 13 5
10 11
8

 

출력
1
1 2 3
1 3 3
1 4 500
1 5 500
2 3 500
2 4 500
2 5 5
3 4 10
3 5 500
4 5 8


입력 

5 6
500 3 500 500
500 500 500
500 500 
500

 

출력
0

 

 

 

 

 

    uzzam
    uzzam
    댓글쓰기

    티스토리툴바