Door

https://www.acmicpc.net/problem/12946 12946번: 육각 보드 크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다. 육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다. 어떤 칸 www.acmicpc.net 이 문제는 어떻게 색을 칠할지 먼저 고려해야합니다. https://astrid-dm.tistory.com/380 백준 12946번 육각 보드 (C++) 문제 링크 : www.acmicpc.net/problem/12946 12946번: 육각 보드 크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다. 육각 보드의 일부 칸을 색칠하려..

알고리즘 공부 2022. 9. 14. 10:40

https://www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 이 문제는 삽질한 과정이 많아서 풀이를 전부 파보겠습니다. 우선 이 문제에서 구현해야할 것. 1. 나무로부터 거리 구하기 2. 최단경로 구하기 1번은 bfs를 써서 구하면 됩니다. 나무를 deque에 받고 bfs로 거리를 구하면 끝. 문제는 2번인데... 우선 처음에 틀렸던 풀이. #백준 2817번 늑대사냥꾼 from collections import deque dx=[0,0,1,-1] dy=[1,-1,0..

알고리즘 공부 2022. 9. 13. 14:23

https://www.acmicpc.net/problem/14947 14947번: 상자 배달 처음 지도의 세로 크기 n과 가로 크기 m이 주어진다(1 ≤ n ≤ 500, 1 ≤ m ≤ 500). 다음 n개의 줄에는 m개의 숫자가 주어진다. 0은 싱크홀이고 1은 땅, 2는 시작지점, 3은 목적지다. www.acmicpc.net 처음에는 중간점을 x,y로 두고 1x1 1x3나누는 건 생각했지만 1x3을 가로,세로로 구현하는 부분이 제대로 되지 않았습니다. 제대로 구현하기 위해서 state==0-->1x1 state==1-->1x3(가로) state==2-->1x3(세로) 이렇게 나눠서 상자가 움직일때를 구현했습니다. #백준 14947번 상자배달 from collections import deque dx=[0..

알고리즘 공부 2022. 9. 13. 11:40

https://www.acmicpc.net/problem/25173 25173번: 용감한 아리의 동굴 대탈출 알쿡 나라의 아리 기사는 드디어 깊은 동굴 속에 사는 전설의 보스 몬스터를 잡으러 왔다. 이후 설명에서 보스 몬스터는 편의상 보스라고 칭한다. 알쿡 나라는 무한히 큰 2차원 격자판으로 이루 www.acmicpc.net 그야말로 '빡구현'문제. 하나 하나 제대로 구현하면 되지만 구현해야할 것이 워낙 많은지라 체감 난이도가 높은 편. 제가 뻘짓했던 것으로 주의사항을 적어보자면 1. 아리,보스는 체력이 0'이하'가 되면 패배. 즉, 0이거나 0보다 작을 때를 봐준다. 2. 문제에서는 '전투중'이라고 애매하기 표현했지만 어떤 상황이든 체력이 0이 되면 패배. 아리같은 경우엔, 방향을 돌리다가 체력이 -1..

카테고리 없음 2022. 9. 12. 19:54

https://www.acmicpc.net/problem/25208 25208번: 새벽의 탐정 게임 새벽의 탐정 게임은 재미있는 2인용 보드게임이다. 한 명은 탐정, 다른 한 명은 도둑 역할을 맡는다. 게임은 $N$행 $M$열 격자 위에서 진행된다. 격자의 각 칸은 벽이 설치되어 있거나 비어있고, 역 www.acmicpc.net 정육면체를 굴리면서 가야해서 체감난이도가 올라갔습니다. 도형굴리는 부분은 진짜 프로그래밍 삐긋~ 해버리면 답이 안나오는 유형이라 돌리는 거 구현하는 것만으로도 스트레스받네요. q에 cube를 받고 1을 바닥면으로 설정. 만약 x,y좌표에 도둑이 있고 cube[1]==1이라면 도둑을 잡은 것으로 설정. 이동하면서 조건에 맞게 cube를 돌려주면 됩니다. #백준 25208번 새벽의 ..

알고리즘 공부 2022. 9. 12. 11:00

https://www.acmicpc.net/problem/24513 24513번: 좀비 바이러스 여기 $N$ x $M$ 격자 모양의 마을이 있다. 어느 날 세상에 좀비 바이러스가 창궐하여 바이러스가 빠르게 퍼져나가버린다. 바이러스에 대해 조사한 결과 세 종류의 바이러스가 존재했으며 각각 $1$ www.acmicpc.net 많이 본 bfs유형과 같지만 다릅니다. 1,2 바이러스가 있고 1,2바이러스가 동시에 퍼집니다. '동시에'퍼진다는 것 때문에 '동시에'퍼트리는 걸 구현해야합니다. "아니, 동시에 퍼지니깐 동시에 퍼지죠. 그게 뭔소리이신가요?" 만약 이 문제가 '바이러스가 퍼진다'라고 했으면 바이러스를 queue에 넣고 bfs계속 돌려주면 문제가 없습니다. 그런데 1,2 각각의 바이러스가 다르고 특히나 ..

카테고리 없음 2022. 9. 11. 23:02

https://www.acmicpc.net/problem/14948 14948번: 군대탈출하기 첫 줄에 각 병영의 세로 길이 n, 가로 길이 m 이 주어진다. (1 ≤ n, m ≤ 100) 다음 줄부터 차례대로 병영의 블록별 레벨 제한 k가 주어진다. (0 ≤ k ≤ 109). www.acmicpc.net 삽질을 참 많이 한 문제. 이 문제는 '도움닫기'입니다. bfs를 해주면서 '벽타고 넘기기'를 해주면 됩니다. 벽을 탈때에는 이동하는 방향 그대로 한번 더 이동해주면 됩니다. #백준 14948번 군대탈출하기 from heapq import heappop,heappush import sys dx=[0,0,1,-1] dy=[1,-1,0,0] N,M=map(int,input().split()) room=[l..

알고리즘 공부 2022. 9. 11. 20:10

https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 이 문제를 처음 풀때는 이렇게 생각했습니다. 1. 로봇을 기준으로 key까지의 거리를 구한다 2. 각 key들간의 거리를 구한다. 1까지는 그렇다치더라도 2에서 시간초과가 엄청날 것으로 보였습니다. key의 갯수가 250개가 된다하면 1->2~250번째 key까지의 거리 2->2를 제외한 나머지 키들까지의 거리 3->..... 이렇게 구하다보면.... 역시나 시간초과..

알고리즘 공부 2022. 9. 8. 00:25