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/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..

아이디어 재귀를 연습하기에 좋은 문제였다. 재귀의 base case는 길이가 1일때이다. (길이가 1일때는 팰린드롬이다.) 길이가 2 이상인 경우는, 문자열을 반으로 나눈다. 길이가 짝수인 경우, 반으로 그대로 나누고, 홀수인 경우는 가운데 문자를 기준으로 반으로 나눈다. 이때 반으로 나눈 문자열 다르다면 바로 "아카라카"의 조건에서 탈락이다. 반으로 나눈 그 문자열을 다시 재귀함수의 인자로 넣음으로서 해당 문자열 또한 "아카라카"인지 검사한다. 반으로 나눈 기준 앞 뒤의 문자열이 모두 아카라카라면 합친 문자열 또한 아카라카이다. https://www.acmicpc.net/problem/23304 23304번: 아카라카 주어진 문자열 $S$가 아카라카 팰린드롬이라면, AKARAKA를 출력한다. 만약 그렇..

n의 입력이 작기 때문에 브루트포스(완전 탐색)으로 풀어도 무리가 없다. 자신보다 키, 몸무게 둘 다 큰 경우 cnt++한다. https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net #include #include #include using namespace std; vector v; int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,x, ans = 0..