Door

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

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 이 문제는 좌표평면에 대해서 다르게 관점을 가지게 해준 좋은 문제입니다. 우선, 이 문제는 백트레킹을 공부하셨더라면 '백트레킹쓰면서 퍼즐 좌표를 다 받아야하는건가?' 라는 생각이 자연스럽게 듭니다. 물론 이 방식이 틀린 방법은 아니지만 메모리를 확~~넘게 됩니다. 그럼 어떻게 숫자를 저장하지?? 구글링해본 결과 퍼즈를 숫자로 바꾸면서 구할 수 있었습니다. 파이썬은 딕셔너리에 숫자를 저장해주어서 dict[숫자]=걸리는 시간 이렇게 저장해주면 문제를 풀어낼 수 있었습니다. #백..

알고리즘 공부 2022. 9. 5. 22:11

https://www.acmicpc.net/problem/2021 2021번: 최소 환승 경로 첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발 www.acmicpc.net 이 문제에서 구현해야할 부분은 '어떻게 경로가 만나는 걸 표현할지'입니다. 처음에 저같은 경우에는 경로의 숫자 하나하나를 탐색하면서 다른 루트에 있는지 확인하는 쪽으로 갔습니다. 근데 이 방식은 경로가 많아질수록 시간초과가 어마어마하게 된다는 단점이 있습니다. 그래서 미리미리미리 '어떤 역은 몇번 경로랑 겹친다' 라는 걸 구현해주면서 문제를 풀었습니다. #백준 202..

알고리즘 공부 2022. 9. 5. 00:00

https://www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 이 문제는 구글링하면서 허탈했던 문제. 아니...뭐야...이렇게 쉬웠다고? 하지만 정작 문제를 처음 접할때는 많이 낑낑댔습니다. 체감상 어렵게 느껴진 부분은 8방향의 좌표를 다 보고 모래성을 무너트리는 것. H와 W의 범위값이 최대 1000이라고 되어있으니 첫,마지막 행과 열을 제외하더라도 최대 999x999x8의 경우를 계산해야합니다. 모래성이 없는 경우는 스킵하더라..

알고리즘 공부 2022. 9. 4. 21:28