yulee

🤔문제 이해 최단거리로 도달할 수 있는 도시들 중 최단거리가 k인 경우만 출력해주는 문제이다. 💡첫번째 아이디어 다익스트라 문제인데 그냥 다익스트라를 수행한 후 최단 거리가 k인 값만 출력해주면 된다고 생각했다. 🔥풀이🔥 다익스트라 수행 후 dist[i]값이 k인 i만 출력 ❌트러블 슈팅 dist를 모두 INF를 바꿔주고 시작점인 x만 0으로 바꿔주는 코드가 없어서 첫 제출에서 틀렸다. dist[x] =0 코드 추가 후 제대로 돌아갔다. #include #include #include using namespace std; #define INF 987654321 int n, m, k, x; vector edge; int dist[300002]; int main() { cin.tie(nullptr); cou..

🤔문제 이해 문제에서 요구하는 1,2,3번을 계산하되 벽에 대한 정보가 1, 2, 4, 8로 주어지는 것으로 보아 비트마스킹을 사용하면 되는 문제이다. 🔥풀이🔥 간단한 BFS를 수행하되 벽의 정보를 비트 연산으로 처리해주었다. ((1 > m; for (int i = 0; i > map[i][j]; } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!visited[i][j]) { visited[i][j] = true; cnt++; q.push({i, j}); room_size = 0; BFS(); if (max_room < room_size) max_r..

🤔문제 이해 비교된 학생들은 그 순서대로 줄을 비교되지 않은 학생들은 그냥 랜덤으로 줄을 세우면 되는 문제이다. 💡첫번째 아이디어 비교되지 않은 학생들을 먼저 맨 앞에 세워주고 비교된 학생들은 "순서"가 정해지므로 그 학생들을 순서에 맞게 줄을 세우는 방식을 떠올렸다. 그냥 위상정렬 문제. 🔥풀이🔥 in_degree의 값이 0인 경우 먼저 queue에 넣어준다. queue가 빌때까지 pop한 학생의 번호를 출력하고 그 학생 다음으로 줄을 설 수 있는 학생의 in_degree를 -1해줬을 때 in_degree값이 0이라면 queue에 push해준다. 비교된 학생이 중복될 수 있으므로 visited를 이용해 이미 줄을 세운 학생은 무시해준다. #include #include #include using nam..

🤔문제 이해 1번 정점에서 N번 정점까지 가는 모든 경로 중에 최대 k개의 도로 이동 시간이 0이 되었을 때 시간이 가장 적게 드는 경로의 시간을 구하는 문제이다. 💡첫번째 아이디어 다익스트라 문제이지만 도로를 포장해야 한다는 점에서 더 어려웠다. 스터디 멘토님이 가르쳐준 방법은 아래 풀이와 같다. 🔥풀이🔥 최단경로 문제에서 최단거리를 저장하는 1차원 배열을 2차원 배열로 바꾸어 dist[i][j]에서 j는 도로를 포장한 횟수를 의미한다. 따라서 다익스트라로 구현하되 j값이 문제에서 주어지는 포장가능한 도로의 개수 k보다 작을 때 도로를 한 번 포장한 값을 j+1에 넣어주고 포장하지 않았을 때의 값을 j에 업데이트 해준다. 정점 n에 도착하면 break해주고 나서는 도로를 몇번 포장했을 때 가장 최소인지..

🤔문제 이해 선행관계가 있는 작업은 선행 작업을 모두 마쳤을 때 수행될 수 있으므로 순서대로 작업하다가 특정 건물의 건설이 완료할 때까지 걸리는 최소 시간을 구하면 된다. 💡첫번째 아이디어 동시에 작업될 수 있는 작업들 중 시간이 적게 걸리는 작업이 먼저 다 수행되어야 하므로 priority queue를 사용하면 된다. 🔥풀이🔥 pq에서 가장 시간이 적게 걸리는 작업을 먼저 수행하고 그 작업 다음에 수행될 수 있는 작업의 in_degree를 하나 줄여준다. in_degree를 줄였을 때 그 값이 0이라면 다음에 바로 수행할 수 있으므로 pq에 현재와 다음 작업의 수행시간을 더한 값과 다음 정점을 넣어준다. 위 과정을 반복하다가 찾고자 하는 작업이 pop될 때 그 작업의 수행시간을 출력해주면 된다. 아래는..

🤔문제 이해 모든 도시를 거치고 다시 처음 도시로 돌아오는 모든 경로 중 비용이 가장 적게 드는 경로의 비용을 구하는 문제이다. 💡첫번째 아이디어 그냥 순열을 구해서 풀면 최대 16! =20,922,789,888,000으로 1초 안에 절대 풀 수 없다. 이 문제는 1주차 스터디에서 배운 비트마스킹에 대한 문제였고, 문제 풀이 방식을 거의 다 배웠어서 DP와 비트마스킹으로 바로 풀 수 있었다. 물론 DP 동작 방식을 이해하기 위해 시간이 조금 걸리긴 했다. 🔥풀이🔥 dp[i][j]는 현재 위치 i와 현재까지 방문했던 정점들의 정보를 담은 j 값일 때, 앞으로 필요한 순회 비용의 최솟값을 의미한다. j가 (1 w[i][j]; } } cout

🤔문제 이해 시작점에서 각 정점을 방문하기 위해 필요한 최소 비용을 구하는 문제이다. 💡첫번째 아이디어 문제가 그냥 딱 다익스트라 문제라 다익스트라를 이용했다. 🔥풀이🔥 다익스트라를 그대로 구현하였고, 다음 정점까지의 거리를 우선순위큐에 넣어주기 전에 이미 그 정점까지 최소거리보다 크면 큐에 넣어주지 않고 continue를 해주었다. 그리고 우선순위큐에 들어있는 정점이 이미 최소거리가 확정되었다면 그 때에도 continue를 해줘서 불필요한 연산을 줄여주었다. 아래는 제출한 코드이다. #include #include using namespace std; #define INF 100000000 int dist[20002], v, e, k; int main() { cin.tie(nullptr); cout.t..