BFS bfs로 풀었음 플로이드 와샬 풀이가 바로 떠올라서 최대한 bfs로 풀려고 노력했다. 즉 어느 하나의 노드를 기준으로 탐색하게 되면, 해당 노드로부터 다른 노드까지의 depth를 bfs로 탐색해가며 구할 수 있다. 시작이되는 어떤 노드를 queue(이하 q로 부름) 에 삽입한다. q를 pop해 그 노드와 인접한 (adj, copy 배열이 1), 방문하지 않은 노드를 그 다음으로 선정한다. 이때 depth를 1씩 증가한다. 이는 시작노드로부터의 depth가 현재 pop한 x(현재 노드)까지의 depth보다 1이 증가함을 의미한다. 다른 말로, 0-1-2 순으로 노드가 있으면, 0-2까지의 depth는 0-1까지의 depth + 1이다. 그렇게 해서 q가 비었다면, 즉 모든 노드를 탐색했다면 저장된 ..

하.. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 글 읽기 - 40% 쯤에서 틀립니다 문제가 뭔지 도저히 모르겠어요... 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net #include #include #include #include #include using namespace std; void kmp(string t, string p, vector &box) { int ans = 0; int i = 0, j = 0..

https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 정-직하게 2차원 배열의 가운데부터 1씩 증가하며 달팽이 모양(상, 우, 하, 좌) 순으로 2차원 배열을 탐색했다. 내가 이미 채운 곳이라면 (이미 어떤 cnt라는 정수가 채워져 0이 아니라면) 왔던 방향을 한번 더 가면된다. 이는 곧 현재의 방향을 나타내는 iterator i를 2 감소하면 된다. 1을 감소하면 되는게 맞지만, 현재 내가 수행한 반복문의 끝에서 1이 증가하므로 그것까지 고려해 2를..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net q.pop()을 빼먹어서 queue 길이가 자꾸만 증가하는 이유를 찾으려 디버깅을 계속했다... ㅠㅠ 76%에서 틀렸었는데, 아무 칸도 물에 잠기지 않을 수 있다는 조건을 빼먹었기 때문이다. 유사 문제 떨어진 영역(뭉탱이)의 개수를 구하는 방법을 모르겠다면 아래 문제와 해답을 참고하면 도움될 것이다. 2021.09.26 - [PS/백준] - 백준 4963번 (C++) 섬의 개수 백준 4963번 (C++)..

https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 아이디어 가려는 칸이 0이면 진행한 칸 수인 cnt+1하고 queue에 넣고, 1이라면 cnt+1, block+1해서 push 했다. 틀림 #include #include #include using namespace std; const int MAX = 1000; int N,M,K; char arr[MAX][MAX]; int dx[] = {-1, 0, 1, 0}..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net bfs로 queue에 현재 노드 번호(cur or i)와, 현재 그 노드가 가진 촌수(cnt)를 pair형으로 기록하며 넣어주었다. 현재 노드와 다음 노드가 인접하다면 (arr[cur][i] 가 1이라면) queue에 cnt+1하여 push한다. 10분만에 아래 틀린 코드를 짜놓고 잔뜩 뿌듯해하며 냈는데 33%에서 틀려서 부랴부랴 고쳤다. 우선 양방향 그래프로 구현되기에 방문체..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 브루트포스로 해결한다 하더라도 시간복잡도는 O(NM)이다. 가능한 모양의 개수 19개를 N*M개만큼 적용하는 것이다! 그러므로 맘 편하게 브루트포스로 해결했다. 다른 풀이를 찾아보니 depth를 5로 정하여 탐색하는 방법도 있는 듯하다. #include #include #include #include using namespace std; // O(NM) const int MAX = 500; int..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 중간에 실수를 많이해서 한시간 반-두시간을 붙잡고 있었다. ㅠㅠ 1. x를 전역변수로 선언해놓고 go()라는 함수에서 지역변수로 또 사용했다. 2. 좌우로 이동하면 y가 증감하도록 해야하는데 내 머릿속 좌우 == 2차평면위의 x축인 나머지 x를 증감하는 실수를 했다. 거의 단순 구현이니 못 풀었다해도 이 글을 읽되, 코드는 최대한 나중에 참고하고 풀어보길 바란다! 문제를 다 풀고 난 뒤 다른 사람들이 푼..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net Bead라는 structure를 만들고, 처음 구슬들의 위치를 기록해 queue에 push한다. 이후 bfs로 탐색하는데, 핵심은 파란 구슬과 빨간 구슬이 동시에 구멍에 빠질 때이다. 이것을 떠올리지 못해 풀이를 참고했다. ㅠㅠ 또 이동하려는 다음 위치가 벽이 아니고, 현위치가 구멍이 아닐 때만 이동할 수 있다. 이 점도 실수했다. 나중에 꼭 다시..

https://www.acmicpc.net/problem/23559 23559번: 밥 제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다. 준원이는 대면 수업이 시작되는 바람에 이제 남 www.acmicpc.net 틀린 코드 #include #include #include #include using namespace std; int n, x; vector v; bool cmp(pair p1, pair p2) { double a = (double)(p1.first) / (double)(p1.second); double b = (double)(p2.first) / (double)(p2.second); i..