문제 링크 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..
문제 링크 1922번: 네트워크 연결 풀이 최소신장트리 문제. 난 union-find 알고리즘으로 풀었다. 간선을 cost 기준으로 오름차순 정렬한다. 각 노드들은 각자의 부분집합으로 자기 자신 값을 넣는다. (subset) 이제 사이클이 생기지 않도록 비용이 적은 간선부터 연결한다. 이 사이클을 확인하는게 union-find이다. unionFind 함수에서는 a노드와 b노드의 부모 노드를 비교하여 같지 않으면(다른 부분집합이면) 연결한 뒤 true를 return한다. parent 함수는 노드의 부모 노드를 찾는 함수인데, 재귀 함수를 통해 따라가서 return한다. merge 함수는 각자 다른 부분집합을 합치는 함수이다. a노드의 부모와 b노드의 부모를 찾아 서로 연결한다. 부모의 숫자가 작은 쪽으로 ..
문제 링크 2252번: 줄 세우기 풀이 위상 정렬 알고리즘을 알아야 풀 수 있는 문제. 모르겠어서 찾아봄 .. 알고리즘 자체는 간단하다. 사이클이 없는 방향 그래프에서 순서를 찾을 때 사용하는 듯하다. 해당 노드로 들어가는 간선이 없어야(다 해치워야) 그 노드를 방문할 수 있는 형태이다. 입력을 받으며 인접 리스트를 만들고 진입 차수 벡터도 만들어준다. 노드 1부터 n까지 확인하는데, 맨 첫번째 순서인 노드를 찾기 위해 진입차수가 0이고, 방문하지 않은 노드라면 위상 정렬을 실행한다. queue에 첫 번째 노드를 넣고, 방문 처리 뒤 queue가 빌 때까지 반복한다. q에서 나온 노드를 출력하고, 해당 노드 cur과 연결된 노드들을 cur과의 간선을 끊었을 때(진입차수를 줄이고), 진입차수가 0이 된다면..
문제 링크 1946번: 신입 사원 풀이 그리디 문제. n이 10^5라서 완탐으로 풀기엔 시간 초과가 남 a와 b를 입력 받으면서 a의 등수 인덱스에 b의 등수를 넣는다. 1등은 무조건 합격이기에, minNum을 1등의 b 점수로 넣고 2등부터 확인한다. minNum보다 arr[i]가 크다는 것은, 나보다 a 점수가 좋은 사람들이 b 점수도 좋다는 뜻이므로 제외한다. minNum은 계속해서 최솟값으로 갱신한다. 예제를 통해 arr를 만들면 이런 식이 될 것이다. a 등수 인덱스 1 (등) 2 3 4 5 6 7 arr (b 등수) 4 (등) 5 6 2 7 1 3 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0..
문제 링크 16234번: 인구 이동 풀이 DFS로 풀긴 했는데, BFS가 편했을 것 같다.. 값을 입력 받으며 벡터를 만든다. 인구 이동이 있어 다시 확인해야 하는지 체크하기 위한 변수 flag가 true라면 계속 인구 이동 시킨다. 첫번째는 인구 이동을 해야하는지 체크해야 하므로 do-while문을 쓴다. 벡터를 돌며 visited[i][j]가 0이면 탐색되지 않았다는 것이므로 dfs 함수로 탐색을 시작한다. dfs 함수에서는 상하좌우를 확인하며 gap이 범위 안에 있다면 재귀 호출을 한다. 영역 내의 총 합을 구하기 위한 sum과 영역 칸의 개수를 구하기 위한 cnt를 갱신한다. 영역 구분이 끝나면 arr의 값을 바꿔줘야 하므로 해당 위치 값을 갖는 unionArr에 추가한다. dfs를 돌고 한 영역..
