반갑습니다!

17472번: 다리 만들기 2 boj.kr 풀이 [프로그래머스] 지형 이동과 유사한 문제인데 개인적으로 조금 더 까다로웠다. 상당히 구현할 것이 많은 문제이다. 해당 문제는 완전탐색으로도 해결할 수 있다고 한다. 아래의 코드는 MST를 사용해서 해결하였다. 이 문제에서 MST를 만들어서 문제를 해결하려면 크게 3단계로 나누어서 풀어야한다. 섬들 라벨링 하기 섬들 간의 거리 구하기 MST 생성하기 우선 섬 라벨링은 BFS 알고리즘을 통해 할 수 있었다. visited[][] 배열을 선언해 중복 방문을 막아주었다. // 섬들을 구분하기 위해 bfs 알고리즘 사용 void bfs(int x, int y, int idx) { queue q; q.push({ x, y }); visited[y][x] = idx; ..

1948번: 임계경로 boj.kr 풀이 이 문제는 위상 정렬과 BFS를 사용해서 해결했다. 우선 위상 정렬을 사용하면 도착 도시까지 걸리는 최대 시간을 쉽게 구할 수 있다. 그리고 나면 관건은 1분도 쉬지 않고 달려야 하는 도로를 세는 것이다. 이는 위상 정렬을 했던 결과를 이용해서 구할 수 있다. 위상 정렬을 수행해서 각 도시까지 도착하는데 걸리는 최대 시간을 알아냈기 때문에 이번에는 도착지에서 출발지로 역행하면서 탐색해준다. 어떻게 도로의 개수를 찾을 수 있는지는 그림을 보면서 이해하자. 위의 그림처럼 1번 도시까지의 최대 시간이 7, 2번 도시까지의 최대 시간이 17이고 1번 도시와 2번 도시 사이의 도로를 건너는데는 10분이 걸린다고 가정하자. 그렇다면 2번 도시에서 1번 도시로 탐색을 할 때 2..

11060번: 점프 점프 boj.kr 풀이 BFS와 동적계획법을 사용해서 해결했다. 현 위치에서 가장 멀리 뛴다고해서 최적해가 되지 않는다. 따라서 현 위치에서 뛸 수 있는 위치들을 모두 queue에 넣어줘서 최소값을 구했다. 코드 C++ #include #include #include using namespace std; int n; vector a, visited; int bfs() { visited = vector(n, 987654321); queue q; q.push(0); visited[0] = 0; while (!q.empty()) { int cur = q.front(); q.pop(); for (int i = 1; i = n) break; // 범위를 벗어나면 멈춘다 if (visited[c..

5567번: 결혼식 www.acmicpc.net 풀이 상근이의 번호가 1번이므로 1번에서 시작해서 BFS로 친구의 친구까지 확인해주면 된다. 코드 C++ #include #include #include using namespace std; int n, m; vector adj; int bfs() { queue q; vector visit(n + 1, false); q.push(1); visit[1] = true; int answer = 0; int count = 0; while (!q.empty()) { int size = q.size(); if (count == 2) break; while (size--) { int current = q.front(); q.pop(); for (int i : adj[c..

1939번: 중량제한 www.acmicpc.net 풀이 시간 초과와 메모리 초과가 발생하기 쉬운 문제이다. 결론부터 얘기하면 DFS + 이분탐색 또는 BFS + 이분탐색으로 해결할 수 있다. 문제를 읽어보면 그래프 탐색 문제이므로 DFS / BFS를 사용해야하는 것은 쉽게 알 수 있다. 그런데 문제에서 C가 최대 1,000,000,000이 되기 때문에 물품의 최대값을 찾을 때 선형 탐색으로는 찾을 수 없다는 것을 알 수 있다. 따라서 Parametric Search (이분 탐색)을 사용해 가능한 물품의 무게를 찾아서 시간 초과를 방지할 수 있다. 그리고 N의 최댓값이 10,000이므로 인접 행렬을 사용하면 메모리 초과가 발생한다. 따라서 인접 리스트를 통해 메모리 초과를 방지해서 해결했다. 코드 C++ ..