synodic의 삭망월

매 칸에 대해서 방문 검사를 하며, 해당 칸이 울타리 안쪽이라면 bfs로 울타리 내부의 늑대와 양의 개수를 세고, return 값으로 늑대와 양을 반환했다. 어떤 칸에 대해 방문하지 않았다고 하면 무조건 bfs로 탐색하였다. from collections import deque import queue from re import T def bfs(a, b): queue = deque([(a, b)]) wolf = 0 sheep = 0 while queue: x, y = queue.popleft() if arr[x][y] == "v": wolf += 1 elif arr[x][y] == "o": sheep += 1 for i in range(4): nx = x + dx[i] ny = y + dy[i] if n..

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로 탐색하는데, 핵심은 파란 구슬과 빨간 구슬이 동시에 구멍에 빠질 때이다. 이것을 떠올리지 못해 풀이를 참고했다. ㅠㅠ 또 이동하려는 다음 위치가 벽이 아니고, 현위치가 구멍이 아닐 때만 이동할 수 있다. 이 점도 실수했다. 나중에 꼭 다시..