0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 어느 섬이던 가장 가까운 다리를 찾는 문제이다. 필자는 아래와 같은 방법으로 해결하였다. 1. dfs로 섬을 라벨링하고, 모서리 부분을 큐에 넣는다. 2. 큐에서 꺼내며 bfs로 최단 거리를 갱신한다. DFS(섬을 라벨링하고, 모서리 부분을 큐에 넣기) main문에서 처음 찾은 부분을 기점으로 dfs를 실행하고, 라벨(임의 숫자)을 붙인다. check 배열을 통해 같은 육지인지 판단..

문제 출처 : https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이 다익스트라로 해결하는 문제이다. 최대 아이템 개수를 구해야 하므로, 모든 지역별로 다익스트라를 돌린 후, 최대 아이템을 갱신하면 된다. 다익스트라 우선순위 큐를 이용해서 구현하였다. void dijkstra(int start) { for(int i = 1; i cost + ncost) { dist[next] = cost + ncost; pq.push({dist[next], next}..

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 최대한 많은 라운드를 진행시켜야 한다. 필자가 생각한 방법은 아래와 같다. 1. 우선 막지 못할때까지 병사를 소모한다. 2. 막지 못할 경우, 가장 많은 병사를 사용했던 곳에 무적권을 사용한다. (priority_queue) 3. 무적권을 다 쓰면 종료한다. 따라서, for문을 순회하며 priority_queue에 병사의 수를 push 하고, 무적권이 있는 경우 우선순위 큐에..

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전형적인 bfs 문제인데, 중간에 레버를 거친 후 출구로 가야한다. 따라서 시작 지점 -> 레버, 레버 -> 출구 이렇게 2번의 bfs를 돌리면 된다. bfs 함수 하나를 선언하고 재사용하는 방식으로 구현하였다. 시작 -> 레버 or 레버 -> 출구 bfs 중 가지 못하는 경우 -1 을 리턴하여 에러를 판별한다. 코드 #include #include #include #incl..