hwooo

https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 BFS로 범위를 훑으며 인접한 노드가 같은 팀일 때 수를 셌다. 해당 문제는 "가로" 길이가 N이다. 코드 #include #include using namespace std; bool map[101][101], visited[101][101]; int N, M; int blue, white; void BFS(int sx, int sy, int team) { queu..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 최단 거리를 찾는 문제이므로 BFS. 벽을 한 번까지는 부술 수 있으므로 현재 상태가 벽을 부술 수 있는 상태인지 아닌지를 구분하여 생각해야 한다. 따라서 BFS를 위해 큐에 넣을 때도 이를 같이 저장해야 하며, 방문 여부와 최솟값을 저장하는 배열 모두 이를 구분해서 저장해야 한다. 만약 구분하지 않고 저장한다면, 향후에 벽을 부셔야 도착할 수 있는 상황에서 이미 벽..

https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 입력 받을 때 양과 늑대의 총 갯수를 세고, 탐색 가능한 지점을 저장했다. 이 지점들을 BFS로 탐색하며 각 조건에 맞게 제거했다.처음엔 '.'인 지점만 저장했는데, 그럴 경우 양과 늑대만 있는 지역은 계산되지 않아 '#'이 아닌 모든 지점을 저장했다. 코드 #include #include #include using namespace std; int ground[251][251]..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 풀이 출발하는 지점에 따라 최장시간이 다르게 나와서 모든 출발 가능한 지점에서 BFS로 가장 먼 거리를 찾았다. 코드 #include #include #include #include using namespace std; bool map[51][51], visited[51][51]; vector V; int Time(int R, int C) { int d[4][2] = { {-1,0},{1,0},{0,..

https://www.acmicpc.net/problem/1639 1639번: 행운의 티켓 첫째 줄에 문자열 S가 주어진다. 문자열 S는 1보다 크거나 같고, 9보다 작거나 같은 수로만 이루어져 있고, 길이는 50보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 시간제한이 2초이고, 문자열의 길이도 50이라 브루트포스로 풀었다. 문자의 총 길이를 찾고, n자릿수에서 나올 수 있는 모든 경우의 수를 계산했다. 또한 행운의 티켓은 정확히 2N자리이므로 자릿수가 짝수일 때만 함수를 실행했다. 코드 #include char s[51]; bool Is_Lucky(int start, int end) { int sum1 = 0, sum2 = 0, mid = (start + end) / 2; for (i..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 반복문을 이용한 계산은 시간초과가 발생해서, 알고리즘 설명대로 분할 정복을 이용한 거듭제곱으로 계산했다.이 과정에서 A는 int형의 범위가 넘어갈 수 있으므로 long long 으로 지정해줬다.(백준에서는 long long형 변수를 %d로 입력받아도 오류가 안 나는데 VS 환경에서는 발생함.) 코드 #include int main() { int B, C; long long int A, sum = 1; scanf("%lld %d %d", &A, &B, &C)..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 풀이 문제의 제목부터 집합이라 set을 사용하려 했으나 수의 범위가 1~20까지이기에 배열을 사용했다. 또한 한 줄씩 입력 받으려고 cin.getline을 사용했는데 시간초과가 발생했고, scanf로 바꾸니 해결됐다. cin은 scanf보다 2배 이상 느리다 하니, 입력 방식의 속도도 이 문제에서는 중요하다. 코드 #include #include #include #include using namespace std; int main(..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 스패닝 트리를 구하는 문제이므로 union-find와 크루스칼 알고리즘을 사용했다. (가중치 오름차순으로 정렬 후 작은 가중치 값부터 더하며 집합을 합쳐주었다.) 음수인 가중치가 있지만, 최단 경로를 구하는 게 아니라 크루스칼이 가능할 거라 판단했다. 코드 #include #include #include using namespace std;..