Doby's Lab

https://www.acmicpc.net/problem/1325 > 사실 이유는 2번이다. 하지만, 접근했던 방법이 1~2번이라 적어보았다. 여담이지만 다익스트라로 돌렸다가 시간 초과가 나왔어서 알게 된 방법이다. [1. 배열의 크기가 너무 크다.] 배열의 크기가 너무 커서 기존의 BFS가 1~N까지 연결되어있나 확인하는 게 메모리 초과를 유발한다고 생각했다. (그럴 수도 있겠지만 방문 체크를 하지 않아서다.) while (!q.empty()) { int front = q.front(); q.pop(); for (int i = 1; i > n >> m; int a, b; for (int i = 0; i > a >> b; map[b].push_back(a); } vector..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 매칭 알고리즘을 배우기 앞서 이분 그래프를 알아두면 좋을 거 같아 공부해보았다. 처음에는 BFS나 DFS로 어떻게 탐색해낼까 생각도 못 했다. (DFS나 BFS가 그래프 탐색 알고리즘이기 때문에) 솔루션을 참고했다. (https://jdselectron.tistory.com/51) 우선 이분 그래프를 보고, 이분 그래프의 특징 하나를 파악할 수 있어야 한다. [문제에 있던 글] 그래프의 정점..

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 답을 구하는 순서는 쉽게 알아낼 수 있었다. 1) 다익스트라를 통해 최단 경로 탐색 2) 해당 최단 경로를 없앰 3) 다시 한번 다익스트라를 통해 최단 경로를 구함 '해당 최단 경로를 없앰'을 해결하는 게 이번 문제의 핵심이다. 솔루션을 참고(https://jaimemin.tistory.com/617)하기도 했고, 바로 전에 풀었던 문제에서 '경로 역추적'이라는 키워..

https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 > a >> b; map[a].push_back(b); map[b].push_back(a); } bfs(1); int cnt = 0; int minValue = INT_MAX; for (int i = 1; i

https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 2차원 배열을 활용하여 BFS로 풀 수 있었다. int emozi[현재 클립보드][현재 화면에 있는 이모티콘 수]; 이렇게 두고 '현재 화면에 있는 이모티콘 수'가 s가 되면 시간이 얼마큼 흘렀는지 출력하게끔 BFS를 짜주면 된다. 3가지 모든 연산의 가중치가 1이라 가능했다. [AC 코드] 의문점 (틀왜맞?): 주어진 범위는 1000 이하가 맞으나 MAX가 1000 + 1인데 되는 이유가 무엇일까..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음엔 BFS를 돌려서 큐에다가 현재의 위치와 벽을 부술 수 있는지에 대한 힘의 여부를 담았다. 그리고, 한번 방문했다면 방문할 수 없게끔 했다. (무한 루프 방지) [처음 코드] #include #include #include #include using namespace std; int n, m; int map[1001][1001] = { 0, }; int temp[10..

https://www.acmicpc.net/problem/14562 14562번: 태권왕 첫째 줄에 테스트 케이스의 수 C(1 ≤ C ≤ 100)이 주어진다. 둘째 줄부터 C줄에 걸쳐 테스트 케이스별로 현재 점수 S와 T가 공백을 사이에 두고 주어진다. (1 ≤ S < T ≤ 100) www.acmicpc.net 이번 문제를 풀면서 저번에 포스팅했던 리모컨 문제가 떠올랐었다. (https://draw-code-boy.tistory.com/99) 솔루션 간단한 BFS 문제였다. S와 T의 점수가 주어지면 두 가지 방법으로 S의 점수를 올려준다. S의 점수가 2배가 된다. 단, T의 점수에는 3점이 추가된다. S의 점수에 1점이 추가된다. 두 가지 경로를 가지고 BFS를 짜주면 된다. 단, 이번 문제에서 주..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 이번 문제는 어떤 특이한 응용력 혹은 논리력이라기보다 수를 잘못 읽어서 발생한 문제에 대해 포스팅한다. 문제는 크게 어렵지 않다. BFS를 돌려서 기존 value에 2를 곱한 것과 value의 뒷자리에 1을 붙여주고, 큐를 돌려서 찾는 값(findValue)이 나오면 종료시켜서 얼마나 걸렸는지 출력하면 되는 문제다. 오류는 10^9를 10억이 아닌 1억으로 봐서 생긴 문제였다. 뒷자리에 1을 넣을 때 value에 10을 곱하고, 1을 더해주기 때문에 1억이 넘으면 안 되기 때문에 조건에 1천만을 안 넘는 value를 다음..