99클럽 코테 스터디 1일차 TIL: 플로이드-워셜

오랜만에 우연히 백준을 들어갔는데 향해99 광고를 보고 스터디 참여 신청을 했다.

취업을 한 뒤 코테 공부를 거의 하지 않아서 기억이 가물가물..
코테 공부하는게 재밌었기도 하고, 공부해야지 해야지.. 하는데 맨날 하지 않아서 스터디라도 해보면 어떨까 생각이 들었다.
대학교 친구 단톡방에 공유해서 한명의 친구와 같이 참여하고 있다.

언어랑 난이도도 선택할 수 있었는데, 나는 Swift/챌린저로 선택을 했다.

챌린저 문제는 다음과 같았다.

문제

https://www.acmicpc.net/problem/11403

 

풀이

기존에 풀어봤던 문제였다.

문제 딱 보자마자 느낀점은 그래프 문제라는 것. 그 이후 모든 경로를 구해야한다는 점에서 플로이드-워셜 알고리즘을 떠올렸다.

플로이드-워셜 알고리즘에 대한 이해만 있다면 쉽게 풀 수 있는 문제라고 생각했다.
근데 플로이드-워셜 알고리즘 기억이 가물가물 했지만
기억나는 부분이 $O(n^3)$ 의 시간복잡도라는 점, 최단 경로 알고리즘이라는 점이 떠올르면서 동작을 떠올리며 코드로 작성해서 풀이했다.

소스코드

후기

문제를 풀고나서 플로이드워셜 알고리즘에 대해 다시 한 번 찾아보고 공부해봤다.
이 문제는 단순히 플로이드워셜 알고리즘을 크게 응용하는 문제는 아니였다.

출근하면서 문제도 풀라니깐 힘들었다.. 하루도 빠지지 않고 꾸준히 할 수 있을까..
이왕 시작한 김에 열심히 해보자..