devlog

출처 : 1068번: 트리 (acmicpc.net) 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 방법 DFS함수의 인자로 index를 받고 재귀 호출하는 방식으로 문제를 풀이하였다. 만약 index가 삭제할 노드의 인덱스인 경우 삭제할 노드의 부모 노드의 자식이 1명일 경우(삭제당하는 노드 하나) cnt를 +1 해주었다. 그리고 return을 함으로써 삭제할 노드의 자식은 탐색하지 않았다 index가 삭제할 노드의 인덱스가 아닌데 자식이 empty인 경우에도 cnt를 +1 해주었다. 다음 자식이..

출처 : 3055번: 탈출 (acmicpc.net) 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 방법 입력받을 때부터 S와 D 지점의 좌표를 기록하고 water의 좌표 벡터에 기록하였다 BFS를 시작할 때 queue에 water의 좌표를 먼저 추가 해준 후 고슴도치의 위치를 que에 넣어 주었는데 이유는 water을 먼저 BFS 하고 그 길을 고슴도치가 갈 수 있냐 없냐 판단을 하기 위해서 이다 (고슴도치를 먼저 이동시키면 동시에 물이 들어오는 경우 복잡해짐) 그런 후 BFS를 돌며 다음 좌표의 board(땅) ..

출처 : 2206번: 벽 부수고 이동하기 (acmicpc.net) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 방법 처음에는 저번에 풀었던 백준 14502번 연구소가 생각나서 완전탐색 + BFS로 풀려고 했으나 이렇게 풀면 시간 초과가 난다 그래서 벽을 부수는데 greedy한 방법이 있을까 생각 해 봤지만 떠오르지 않아 다른 분들의 풀이를 보니 큐에 추가할때 3차원으로 x, y좌표와 추가적으로 이까지 오면서 벽을 부수었는지 기록해 주었다. 결국 큐에 추가해주어야 하는 경우는 ..

출처 : 10026번: 적록색약 (acmicpc.net) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 방법 적록색약이 아닌 경우는 일반적인 BFS 풀이하면 된다 하지만 적록색약인 경우는 R, G인 경우를 판단하여 불린 값에 넣어 두고 따로 이런 경우를 빼내어서 R,G을 같은 색으로 취급해주었다. BFS1이 적록색약이 아닌경우 함수 BFS2가 적록색약인 경우의 함수이다. visited를 중간에 0으로 초기화해주어야 BFS1과 BFS2 가 섞이지 않는다 #include #define pii pair..

출처 : 2667번: 단지번호붙이기 (acmicpc.net) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 방법 BFS를 이용한 완전 탐색 문제이다 이중 for루프를 돌며 방문하지 않았으며 집인 곳이 보이면 BFS를 그 지점 부터 시작하여 연결된 덩어리의 개수를 세어주면 된다. 실수 for (int i = 0;i < N;i++) { for (int j = 0;j < N;j++) { if (board[i][j] == '1') { if (visited[i][j] == 0) { house_num.push_ba..

출처 : 2178번: 미로 탐색 (acmicpc.net) 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 방법 BFS문제로 1,1에서 시작하여 N, M까지의 최단 거리를 구하는 문제이다 que에서 pop을 한 뒤 이 좌표가 미로 좌표 내의 좌표인지 확인하고 그 좌표자리가 벽인지 길인지 확인한 후 길이면 이전 거리(dx, dy를 더 해주기 전)에 + 1을 해준후 배열에 저장하고 자신 좌표를 que에 넣어 주는 방법으로 반복한다. #include using namespace std; int dx[4] = {0, 0, -1, 1}; int ..

출처 : 18405번: 경쟁적 전염 (acmicpc.net) 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 해결 방법 BFS 문제이다. 처음에는 번호가 작은 바이러스의 종류부터 증식을 시키기 위해 BFS의 매 초마다 우선순위 큐를 사용하여 board를 탐색하여 추가해주었는데 이런 식으로 작성하니 시간 초과가 난다 생각해 보면 맨 처음에만 번호가 작은 바이러스의 종류 순으로 queue에 넣은 후 BFS함수를 돌며 추가해 주어도 자동으로 번호가 낮은 순서대로 계속 추가된다는 것을 알..

문제 : 18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 방법 그래프에서 최단 거리를 찾는 문제이다 최단 거리를 찾는 문제는 bfs를 생각해 볼 수 있다. 처음에는 edge의 입력을 이차원 list를 만들어서 연결되어있으면 1 안 되어 있으면 0으로 풀었는데 이러면 메모리 초과로 틀리게 된다 그러므로 2차원 벡터로 i 에서 j로 가는 edge가 있으면 edge[i].app..

문제 첫째 줄에 N M K 가 주어지고 둘째 줄에 N개의 자연수가 주어진다. N개의 자연수 배열중 M개로 만들 수 있는 가장 큰 수를 만들어서 출력하라 각 배열의 값은 반복 가능하고 같은 인덱스는 K번 초과해서 연속해서 나오면 안 된다 같은 수라도 인덱스가 다르면 연속하여 놓을 수 있다 예를 들어 3, 4, 3, 4, 3 이면 인덱스 1번과 3번은 다른 수이므로 정답은 4 * M가 될 것이다. 풀이 방법 배열을 정렬을 해서 가장 큰 수와 두번째로 큰 수를 결정한다 만약 가장 큰 수가 2개 이상이어도 상관없이 진행 그런 후 가장 큰 수를 만드는 패턴을 보면 K개의 가장 큰 수가 연속해서 나오고 두번 째로 큰 수가 한 번 나오고 다시 가장 큰 수가 k번 나오는 식으로 반복 되야 가장 큰 수를 만들 수 있다...

출처 : algospot.com :: NUMB3RS algospot.com :: NUMB3RS 두니발 박사의 탈옥 문제 정보 문제 위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았 algospot.com 풀이 방법 dp 문제이다. 마을의 정보를 입력받으면서 deg를 계산해주어 각 마을이 연결된 통로를 계산해준다. 기저 조건으로 days == 0 일 때 지금 위치가 목표지점이면 1.0을 리턴 아니면 0.0을 리턴하여 그 값에다 deg를 나누어 주어 확률을 계산하다. 기저 사례가 아닌 경우는 연결된 마을로 이동하는 재귀 호출을 하여 그 값에 deg를 나누어 주어서 확률을 계산한다. #include #inclu..