프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : BFS 풀이 시간 : 17분 문제 풀이 각 부대원들이 여러 지역에서 임무를 수행중이다. 임무가 끝나고 부대로 복귀하는데 걸리는 최단 시간을 부대원 별로 구해서 출력하자.  문제의 제한사항을 확인해보면 꽤나 빠듯하다. 먼저, [전체 정점 ≤ $100000$], [간선(roads)의 개수 ≤ $500000$], [병사의 수 ≤ $500$] 으로 주어졌기 때문에, 각 부대원 별로 한 명 씩 최단거리를 찾아주게 된다면 $O(500 * (100000 + 500000))$으로 시간이 오래 걸리게 된다. 따라서, 부대원 별로 ..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : DFS 풀이 시간 : 28분 문제 풀이 서로 다른 번호가 매겨진 등대 `n`개가 존재한다. 또한, 등대와 등대 사이를 오가는 뱃길이 `n - 1`개 존재하여 모든 등대는 서로 연결되어있다. 등대와 등대 사이를 오가는 뱃길을 밝히기 위해 양 등대 중 적어도 하나는 켜져있도록 등대를 켜 두어야 한다. 켜 두어야 하는 등대 개수의 최솟값을 return하자.문제에서 가장 중요시 되는 부분은 "두 정점 중 적어도 하나는 켜져있어야 된다"라는 점이다.위 예제를 살펴보면, 불이 켜진 노드에는 여러 자식노드가 있음을 확인할 수 ..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : 그래프 탐색, 다익스트라 풀이 시간 : 31분 문제 풀이 n개의 지점으로 이루어져 있는 양방향 통행이 가능한 등산로가 있다. 당신은 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 한다. 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 한다.해당 규칙을 지키면서 intensity가 최소가 되는 등산코스를 정해보고, [등산 코스의 산봉우리 번호, intensity의 최솟값] 배열을 리턴하자. 문제에서 생각해볼 주의..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : 그래프 탐색, BFS, 다익스트라 풀이 시간 : 47분 문제 풀이 자동차 경주에 필요한 경주로를 건설해야 한다. 경주로는 상, 하, 좌, 우 인접한 두 빈 칸을 연결하여 건설할 수 있다.이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 하고, 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부른다. 직선 도로 하나를 만들 때는 $100원$이 소요되며, 코너를 하나 만들 때는 $500원$이 추가로 든다. 경주로를 건설하는 데 필요한 최소 비용을 구해보자.문제의 제한사항을 먼저 살펴보..

https://www.acmicpc.net/problem/2458 난이도 : 골드 4 알고리즘 유형 : 그래프탐색, BFS 풀이 시간 : 39분 문제 풀이 문제의 입력으로 주어지는 정보는 자신보다 키가 큰 사람의 정보이다. 또한, 이를 단방향 그래프로 연결할 수 있다. 문제에서 물어보고자 하는 것은 자신의 위치를 정확히 아는 사람의 수 이기 때문에, 한 정점에서 다음 정점의 개수와 이전 정점의 개수를 모두 알아야한다. 따라서 나는 정방향 그래프와 역방향 그래프를 생성하여, 각 정점에서 모두 BFS 탐색을 진행한 뒤, 모든 탐색이 끝나고 $현재 정점의 개수 == N - 1$인 경우의 개수를 체크하여 정답으로 출력하였다.그림으로 나타내면 다음과 같다. 코드/*두 학생의 키를 비교한 결과의 일부가 주어짐.N명..

https://www.acmicpc.net/problem/2660 난이도 : 골드 5 알고리즘 유형 : 그래프탐색, BFS 풀이 시간 : 22분 문제 풀이 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.문제 설명이 조금 헷갈리게 되어있었지만, 잘 읽어보면 궁극적으로 각 회원의 점수는 다른 회원을 만나기까지의 깊이(Depth)와 같다고 생각하면 된다.이를 그림으로 표현하면 다음과 같다.( 검정 숫자 : 정점의 번호 | 빨간 숫자 : 방문 시간 )1번 회원이 모든 회원을 만나는..

https://www.acmicpc.net/problem/1389 난이도 : 실버 1 알고리즘 유형 : 그래프탐색, BFS풀이 시간 : 26분 문제 풀이 문제를 간략히 요약하자면, "한 사람이 모든 사람을 만나는 데 걸리는 비용이 가장 적은 사람을 찾아라"이다.정점 N의 범위가 작았고(N ≤ 100), 모든 사람의 경우를 구해야 하기 때문에 BFS를 사용하여 값을 구한 뒤, 최솟값을 비교하면 될 것이라고 생각하였다.최솟값 비교의 경우, BFS를 진행하며 방문한 다른 정점과의 거리를 모두 더한 뒤 거리의 합을 비교하는 방식을 사용하였다. 위 문제를 풀며, 효율성을 높이기 위해 다음과 같은 방법을 사용하였다.정점의 합을 계산해 주는 과정에서 이전에 계산된 정점의 합보다 커지게 된다면, 그대로 함수를 종료하도..