개발 블로그

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 풀이를 하기 전에 이분 그래프에 대해 간략히 설명드리겠습니다. 이분 그래프 (Bipartite Grpah) 그래프의 한 종류로, 인접한 꼭짓점을 서로 다른 색으로 칠할 때 두 가지 색으로만 칠할 수 있는 그래프 꼭짓점들의 집합 V와 변들의 집합 E로 이루어진 그래프 G = (V, E)가 이분 그래프라면, 꼭짓점들의 집합 V가 두 집합 A, B(두 개의 그룹)로 나눠져 E에 속한 모든 변들이 ..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 오랜만에 알고리즘 트리 문제를 풀어봤습니다. 이 문제는 트리에서 임의의 두 정점 사이의 가장 긴 거리를 출력하는 문제입니다. 입력의 경우 시작 정점(from)이 주어지고, 시작 정점과 연결된 정점(to)과 두 정점 사이의 거리(dist)를 입력으로 받습니다. 더불어 해당 정점에서 입력을 종료하려면 -1을 입력으로 받아야 합니다. 첫 번째로, 우선 임의의 정점에서 가장 거리가 먼 노..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리(tree)란 ? 그래프(Graph)의 일종으로, 한 노드에서 시작해 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프입니다. 최상단 노드를 루트노드, 자식이 없는 노드를 리프노드라고 합니다. 이 문제는 노드의 개수 n이 주어지고, n에 해당하는 부모노드 인덱스를 입력으로 받습니다(부모 노드가 없는 경우에는 -1) 마지막으로 삭제할 노드를 입력 받고, 이러한 과정을 ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 일반적인 BFS탐색 문제와 크게 틀에서 벗어나진 않지만, 벽(1)을 한 번 이동할 수 있는 조건에서 큰 차이를 보입니다. 그리고 이 조건으로 인해 조금 더 어려워졌습니다. 저는 입력을 2차원 배열로 받고, 구하고자 하는 최단경로를 3차원으로 만들어줘서 풀었습니다. 왜냐하면 벽을 부순 경우가 최단 경로가 될 수 있고, 부수지 않은 경우가 최단 경로가 될 수 있기 ..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net BFS +DFS알고리즘을 활용하면 되지만 조건이 굉장히 까다로운 문제입니다. 벽을 부순 후 벽을 기준으로 이동할 수 있는 영역이 몇 개 인지 탐색하는 문제입니다. 이것을 일일이 탐색한다면 시간 복잡도가 O((MN)^2)으로 매우 오래 걸리게 됩니다. 그래서 이동할 수 있는 영역에 대해서 그룹을 짓고 그룹의 크기가 담겨있는 vector를 만들어 줍니다. 그리고 해당 벽을 기점으..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 기본적인 BFS문제와 유사한데, 높이가 주어져서 2차원이 아닌 3차원으로 표현해야 합니다. 더불어 이동 방향도 상, 하, 좌, 우에서 앞, 뒤가 추가된 6가지로 표현할 수 있습니다. 이동 방향이 행, 열, 높이 총 3개가 있으므로 원소를 3개 참조해야 합니다. 이러한 경우에 c++에서 제공하는 tuple 헤더를 이용해서 해당 원소를 한 번에 참조할 수 있게 되고 굉장히 편리..

https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 가장 기본적인 BFS 문제입니다. 이동 경우의 수가 보기와 같이 6가지 이고, 인접 노드를 방문하면서, 연산 횟수를 하나씩 증가시켜주면 끝나는 문제입니다. 개인적으로 BFS 입문 문제로 괜찮은 문제라고 생각합니다. #include #include #include using namespace std; int mov[6][..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 이 문제는 BFS라고 볼 수 있습니다. 시작 값과 끝 값을 두고 D(num*2 % 10000), S( s-1 > 0 ? 9999 : s-1), L(자리수 왼쪽 한 칸 이동), R(자리 수 오른쪽으로 한 칸 이동) 연산을 하는데, 시작 값에서 끝 값을 만들기 위한 연산의 최솟값을 구하는 문제입니다. 3 1234 3412 1000 1 1 16 테스트케이스를 예시로 들면, 1234에서 34..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제는 뱀과 사다리에 대한 정보가 주어지고, 사다리는 해당 칸에서 위로 올라갈 수 있지만, 뱀은 아래로 내려가는 구조입니다. 만약 사다리나 뱀을 만나지 않는다면, 주사위를 던져 나올 수 있는 모든 경로를 탐색하면 됩니다(6가지) #include #include using namespace std; int dist[101]; int nex[101];..

https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 이 문제는 동전을 하나만 떨어뜨리기 위한 최솟값을 구하는 문제입니다. 만약 횟수가 10번 넘기거나, 동전이 둘 다 떨어지는 경우는 -1을 출력해야 합니다. 코드로 설명드리겠습니다. #include #include using namespace std; int n, m; string a[20]; int mov[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; int go..