문제 링크 https://school.programmers.co.kr/learn/courses/15009/lessons/121690 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제를 보면 바로 bfs를 통한 최단거리 해결책이 떠올랐을 것이다.(1칸 이동의 비용이 '1'로 고정된 단위 길이이기에, 다익스트라를 사용할 필요가 없다.) 이 문제는 약간의 변형으로, 일회성으로 2칸을 이동가능한 "신발" 이 존재하기에, 이를 고려해야한다. 일반적으로 point가 2개의 좌표값, 거리만 있는 것에 반해, 여기서는 일회성 아이템인 "신발" 의 사용 ..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 이 문제를 처음 보고선, 단순하게 시작점부터 각 노드간의 최단 거리를 모두 찾고, 그 중 가장 긴 거리의 수를 고르려고 했다. 이 방법엔 2가지 솔루션이 있다. 1) 시작점에서 각 노드간의 거리를 다익스트라로 구하기: [ V*O(V^2) == O(V^3) ] 2) 플로이드 와샬로 각 정점들간의 최단 거리 모두 구한 뒤, 시작점에서 각노드간 최단거리만 사용하기 [O(V^3)] 하지만, 주..
시작하기에 앞서, 기초적인 구현 방식, 정보들은 최대한 글에서 다루지 않을 예정이고, 혼동되거나 헷갈리는 부분들, 놓치고 넘어가기 쉬운부분들만 설명할 것임을 유의해주세요..! 그래프 탐색이 필요한 이유는 바로 선형적인 탐색 (for문을 통한 i:1~n) 으로 탐색하지 못하는 문제들을 탐색하기 위해서이다. 예를들어 그래프 탐색이 필요한 문제중 하나인 백준 2178 "미로 탐색" 을 보자. 우리는 점차 증가하는 인덱스를 통한 탐색이 아닌, 갈 수 있는 위치로 향하는 탐색을 해야하는데, 이는 for문과 적합하지 않다. 그렇기에 우린 이러한 갈 수 있는 방향을 "그래프" 로 만들어나가며 탐색을 해나가는 것이다. 그래프의 대략적인 정의는 정점, 그리고 간선으로 이루어진 대충 아래 그림 같은 친구들을 말한다. 그래..
