본문 바로가기

백준154

백준 17135 c++ "캐슬 디펜스" -[PlusUltraCode] https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net [필자 사고] 이 문제는 구현 문제이다. 난이도가 높은 문제이다. 필자는 처음에 궁수의 자리를 어떻게 배치해야 할까를 고민하다 조합을 이용하여 이 부분을 해결했다. 그 다음 적을 죽이는 경우를 생각해보자 적이 사정거리 안에 있으면 죽일 수 있다. 이 부분을 우선순위 큐에 넣어 가장 가까운 적부터 죽이고 거리가 같다면 왼쪽에 더 가까운 적부터 죽이는 형식으로 코드를 작성했다. 또한 궁수가 공격을 멈추었다면 적.. 2024. 3. 11.
백준 1600 c++ "말이 되고픈 원숭이" -[PlusUltraCode] https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net [필자 사고] BFS() 탐색 문제이다. 이 문제의 특이한 점은 말의 능력을 사용할 수 있다는 점이다. 처음 필자는 문제를 풀 때 visted를 2차원 배열로 구현하고 문제를 풀었지만 우선순위큐가 너무 과도하게 많이 만들어진 결과 메모리 초과의 문제를 만들어냈다. 핵심은 visted를 3차원 배열로 구현해 우선순위 큐가 과도하게 만들어지는걸 방지해야 된다. [소스 코드] #incl.. 2024. 3. 8.
백준 2638 c++ "치즈" -[PlusUltraCode] https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net [필자 사고] BFS 탐색 문제다. 이 문제의 핵심 풀이는 외부 공간과 치즈 내부 공간을 구별해야 된다. 인덱스 0,0은 확정적인 외부공간이므로 BFS탐색을 이용해 외부 공간을 방문처리를 해준다. 다음으로 치즈가 있는 곳에서 외부공간과 접촉한 갯수가 2개 이상인 경우 배열을 변경해주면 풀이는 완성이다. [소스코드] #include #include #include using namesp.. 2024. 3. 7.
백준 2146 c++ "다리 만들기" -[PlusUltraCode] https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net [필자 사고] BFS탐색문제이다. 먼저 각 섬을 고유의 번호로 분리 시켜야 한다. 필자는 한번의 BFS 탐색을 이용해 분리시켰다. 다음으로 고유의 땅과 바다가 인접한 sero와garo 인덱스들을 찾아 최단거리 알고리즘을 이용하여 전체 탐색 해주었따. 시간복잡도를 계싼해보면 O(N^3logn) 으로 생각이 든다. [소스 코드] #include #include #include using namespace .. 2024. 3. 6.

티스토리툴바