기출문제 2

[BOJ] 17135. 캐슬디펜스

www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제: 캐슬디펜스에서 궁수가 얼마나 많은 적을 죽일 수 있는가? 문제 이해하기!! 한 바둑판에 병사들 여러개 놓고 1초 지날 때마다 한칸씩 전진하는데 마지막 칸의 밖의 칸에서 궁수가 대기타고 있고 그 대기타는 궁수의 범위안에 적이 들어오면 궁수는 쏴 죽입니다. 근데 궁수도 1초에 한 번씩 밖에 못 죽여서 모두를 죽일 수 없는 경우가 생깁니다. 그 때문에 이 문제가 생겼습니다. 즉, 궁수가 있는 칸까지 병사들이 온다면 그 ..

Study/BOJ 2021.02.03

[BOJ] 17471. 게리맨더링

처음에는 하.. 이걸 어떻게 풀어야 하나 생각했는데 보니까 N이 10개더라구요. 그래서 바로 브루트포스로 돌렸습니다!! ㅎㅎ 그러다가.. dfs로 돌리고 페일.. ㅠㅠ 그리고 bfs로 바꿔서 성공했습니다. (나중에 알았지만, dfs도 풀 수 있는데 하... 제가 다 만들어 놓은 코드에서 합계 계산을 잘 못 했더라구요 ㅠㅠ 까빙..) 풀이 방법은 각각의 N-a와 a개의 도시 조합을 나누어서 브루트포스를 돌리면 됩니다. dfs / bfs 방법 둘 다 가능한데, bfs가 쉽습니다... ㅎㅎ bfs 추천 드릴게요! 코드: from itertools import combinations def bfs_com(x, cnt): global res1 Q = connect.get(x)[:] while Q: tmpp = Q..

Study/BOJ 2021.02.02
반응형