문제 링크 2146번: 다리 만들기 풀이 BFS 문제 섬에 대해서 BFS를 돌리면서 섬의 종류를 나눠준다. 육지에 대해 바다 옆에 있는 육지라면 q에 해당 육지를 넣어주고, 해당 거리부터 시작하기 위해 dist 값은 0으로 넣어준다. 다리를 짓기 위해 BFS를 돌릴건데, 해당 다리가 어느 섬에서부터 지어진건지 체크하며(island), 같은 섬에서 지어진 다리라면 continue, 다른 섬에서 지어진 다리라면 그 두 개의 다리를 이어주면 된다. (dist[ny][nx] + dist[ty][tx]) 3번의 경우의 수가 다 아닐 경우 바다이기 때문에 dist와 island를 갱신해주고 q에 넣어준다. 3번에서 두 개의 다리를 이어준 것 중 최솟값을 출력한다. 코드 #include #include #includ..
문제 링크 4179번: 불! 풀이 BFS문제인데 접근 방식이 헷갈렸던 문제 불에 대한 BFS 탐색으로 모든 길에 대한 dist를 구하고, 지훈이는 그 dist를 토대로 BFS탐색을 해야한다. 또, 불은 2개 이상 있을 수 있어 거리에 대해 불이 올 최소 시간을 구해야 하는데, 이는 큐에 불 초기 위치를 바로바로 push해주면 된다. 나는 여기서 불 하나씩 탐색을 해서 헷갈렸음 코드 #include #include #define INF 1000001 using namespace std; char board[1001][1001]; int fireDist[1001][1001]; int dist[1001][1001]; int r, c; int jy, jx; int dy[4] = { -1, 0,1,0 }; int..
문제 링크 10799번: 쇠막대기 풀이 스택 응용 문제 i가 str.size()-1이 아니라면 레이저인지 체크한 뒤, 레이저라면 answer에 현재 스택에 있는 막대기의 수를 더해준다. ()가 한 세트이기 때문에 i++도 해준다. (라면 stk에 push한다. )라면 stk에서 pop하고, answer에 1을 더해주는데, 예를 들어 막대기가 두 개의 레이저로 인해 잘렸다면 레이저 수 + 1로 3등분 되기 때문에 이를 위한 계산이다. 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string str; cin >> str; int answer = 0; stack stk; fo..
문제 링크 6198번: 옥상 정원 꾸미기 풀이 스택 응용 문제.. 어렵다 sum을 구할 때 int로 하면 틀린다. long long으로 해줘야 함 입력값을 거꾸로 스택에 넣어주기 시작한다. 현재 값을 stk의 top과 비교해서 작으면 pop하고 second를 더해준다 여기서 second는 현재 값을 포함한 지운 수가 된다. tmp에는 현재 값에서 볼 수 있는 옥상의 수가 된다. 현재 값을 stk에 push한다. second는 현재 값을 포함해야 하므로 지운값+1(tmp+1)이 된다. cnt에 tmp를 더한 뒤 출력한다. 코드 #include #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int..
문제 링크 14890번: 경사로 풀이 구현 문제 길은 세로, 가로로 있기 때문에 입력받으면서 arr1에는 가로, arr2에는 세로를 넣는다. 한 줄씩 길을 체크할 것이다. 먼저 현재 길인 i와 다음 길인 i+1을 비교해간다. 경사가 같을 때는 continue 1 올라가는 경우 (arr[i]+1 == arr[i+1])에는 앞에 i부터 l개를 확인하며 범위를 벗어나거나, 경사의 차이가 나서 경사로를 못놓거나, 이미 지어진 경우에는 return 0을 한다. slope[i] = 1을 해서 경사로를 넣는 것을 빼먹지 않는다. 1 내려가는 경우 (arr[i]-1 == arr[i+1])에는 뒤에 i+1부터 l개를 확인하며 3번과 같이 return하고 경사로를 놓는다. 1,2,3번 경우가 아니라면 경사의 차이가 2 이..
문제 링크 9370번: 미확인 도착지 풀이 문제가 복잡해보이지만 1504번 풀었다면 그렇게 어렵지 않은 문제 최단 경로에서 특정한 노드를 지나는 최단 경로를 구하는 문제이다. 값을 입력받으며 인접 리스트를 만든다. 루트 3개를 비교할텐데 s -> g -> h -> 후보지, s -> h -> g -> 후보지 중 작은 값과, s -> 후보지 값을 비교해서 같다면 해당 경로를 지났단 뜻이므로 answer에 추가해준다. 루트를 지나는 경로의 길이를 구할 때는 다익스트라 알고리즘을 사용한다. 출발 노드에서 모든 노드까지의 거리는 무한대로 만든뒤, 자신의 노드 dist만 0으로 만들어준다. 우선순위 큐를 이용하여 거리가 작은 노드부터 순서대로 방문한다. 해당 노드를 방문할 때 거리가 최소로 갱신된다면 pq에 넣고 ..
문제 링크 1504번: 특정한 최단 경로 풀이 다익스트라로 푸는 최단 경로 문제. 1 -> u -> v -> n과 1 -> v -> u -> n을 비교하면 되는 문제 입력 받으며 인접리스트를 만든다. 위에서 설명한 루트대로 다익스트라로 최단 경로를 구한다. 다익스트라는 거리 벡터를 모두 무한대로 초기화 하고 현재 시작할 노드를 0으로 만들고 현재 노드부터 우선순위 큐에 넣어 시작한다. dist의 값이 최소로 갱신될 때마다 pq에 노드를 넣어준다. 그렇게 while문이 끝나면 dist에 현재 노드부터 각 노드까지 최소 거리가 만들어질 것이다. 도착 노드를 return 그렇게 두 개의 루트의 값을 구해 최솟값으로 출력해주는데, 이 값이 무한대보다 크거나 같다면 -1을 출력한다. 코드 #include #inc..
문제 링크 입국심사 풀이 이분탐색으로 푸는 문제.. 떠올리는 게 어렵다.. 기준은 제일 빠르게 처리하는 1분과 가장 느리게 처리하는 심사관 * n이 될 것이다. 이 둘을 left와 right로 잡는다. 여기서 주의할 것은 long long 타입이기 때문에 right를 만들 때 int * int형으로 곱해져 int형이 나오기 때문에 형변환을 해주어야 함 mid는 left와 right의 중간 값을 잡고 이분 탐색을 시작할텐데, 이 기준은 mid시간에서 몇 명의 사람이나 처리할 수 있느냐로 본다. cnt가 n보다 크거나 같으면 right의 범위를 줄여주고 answer를 갱신해주고, 작으면 left의 범위를 키워준다. left의 위치가 right보다 작거나 같을 때까지 반복해준 뒤 answer를 출력한다. 코드..
문제 링크 롤케이크 자르기 풀이 set으로 풀었는데 시간 초과가 나서 힌트를 얻은 문제 굳이 기준을 잡아서 할 필요 없이 둘로 나누는 것이기 때문에 기준에서 하나씩 빼면 된다. set1에 toppings를 다 넣는다. 이 때 토핑의 개수를 생각해야하기 때문에 cnt 벡터로 토핑의 개수를 세준다. 이제 토핑을 하나씩 빼서 set2에 넣어줄텐데, 하나 뺀 토핑의 개수가 0일 경우 set1에서 지워준다. set1과 set2의 사이즈를 비교해서 같다면 answer++ 해준다. 코드 #include #include #include using namespace std; int solution(vector topping) { int answer = 0; set set1, set2; vector cnt(topping...
문제 링크 1922번: 네트워크 연결 풀이 최소신장트리 문제. 난 union-find 알고리즘으로 풀었다. 간선을 cost 기준으로 오름차순 정렬한다. 각 노드들은 각자의 부분집합으로 자기 자신 값을 넣는다. (subset) 이제 사이클이 생기지 않도록 비용이 적은 간선부터 연결한다. 이 사이클을 확인하는게 union-find이다. unionFind 함수에서는 a노드와 b노드의 부모 노드를 비교하여 같지 않으면(다른 부분집합이면) 연결한 뒤 true를 return한다. parent 함수는 노드의 부모 노드를 찾는 함수인데, 재귀 함수를 통해 따라가서 return한다. merge 함수는 각자 다른 부분집합을 합치는 함수이다. a노드의 부모와 b노드의 부모를 찾아 서로 연결한다. 부모의 숫자가 작은 쪽으로 ..
