amaranthine

https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 구슬 탐색을 위한 델타값과 블리자드 마법을 위한 델타값이 다르다는 조건을 제대로 안 읽어서 꽤나 고생했던 문제다. 구슬을 일단 큐에 다 담고 터트려주는 방식을 택했는데 당연하게도 Python으로는 시간초과가 난다. PyPy로는 맞았는데, 다른 사람의 풀이를 보니 투포인터를 이용하여 구현한다면 Python으로도 충분히 돌아갈 것 같다. 그리고 중간에 인덱스 에러가 났는데 이는 큐가..

https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 이번에도 deepcopy를 이용해서 원래 맵을 복사해주고, 복사본으로 작업한 뒤 이를 원래 맵에 덮어씌우는 식으로 진행해야 간편하게 풀리는 문제였다. 일단 2차원 리스트를 가지고 이것저것 작업해야하는 문제는 무조건 deepcopy로 배열을 복사해두고 푸는 걸 제일 우선으로 생각해야겠다. 문제가 길고, 설명이 복잡해서 처음에 문제 이해하는 데에만 오래 걸..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 구현 + 백트래킹 문제인데, '백트래킹 시 이전 상태로 되돌아가야 한다' 라는 걸 생각하지 않고 짜서 꽤나 삽질했다. {물고기 번호:[물고기 y좌표, 물고기 x좌표]}로 구성된 딕셔너리와, maps[y좌표][x좌표] = [물고기 번호, 물고기 방향] 으로 구성된 2차원 배열을 이용하였다. 딕셔너리는 물고기 번호 순서대로 물고기가 이동하기 때문에 key를 이용해 물고기 위치를 파악..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net bfs 구현 문제로, 이 문제를 풀 때 주의해야할 점이 몇 가지 있다. 1. 아기 상어의 위치를 나타내주는 9를, 아기상어를 찾은 즉시 0(빈칸)으로 바꿔주어야 한다. 그렇지 않으면 9 크기의 물고기가 있다고 인식해버린다. 2. 먹을 수 있는 물고기를 저장하는 리스트를 따로 만들어서 거리가 같은 모든 물고기를 넣어야 하며, 물고기가 위치한 거리보다 먼 곳은 탐색하지 않도록 조건을 제대로 주..

https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 통나무를 받은 순서대로 통나무의 번호가 매겨지므로, 통나무를 받을 때 좌표와 함께 idx를 저장한다. 그러면 통나무 리스트에는 [x1, x2, y, 통나무 번호]가 들어있게 된다. 이렇게 받은 리스트를 통나무의 x1 (제일 첫부분 좌표)로 정렬해준다. 만약 [[4, 9, 3, 0], [3, 5, 7, 1], [1, 3, 5, 2]] 과 같은 arr가 만들..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 제목 그대로 MST를 구하면 되는 문제이다. 처음에는 prim을 이용해 구현했는데 시간초과, 메모리초과가 나길래 크루스칼로 바꿔 풀었다. import sys input = sys.stdin.readline def find_p(x): if x != team[x]: team[x] = find_p(team[x]) return team[x] else: ret..

https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 크루스칼을 이용해 간단하게 풀 수 있다. 만약 해당 노드끼리 성별이 같으면 continue로 넘어가주고, 성별이 다르다면 이어준다. edge_num으로 이어진 간선의 개수를 세어주고, 중간에 모든 정점이 이어지면 break를 해준다. 만약 주어진 간선을 이용해 정점을 이었는데도 모든 정점이 이어지지 않았다면 edge_num의 개수를 체크하여 -1, 모두 이..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 유니온-파인드로 풀었다. 역시나 부모 찾기는 경로 압축을 이용했다. 입력이 좀 이상하게 주어져서.. 코드가 더럽게 나오긴 했지만.. 일단 주어진 사람들끼리 union 해주고, 진실을 아는 사람이 없으면 파티의 개수를 바로 출력한다. 진실을 아는 사람이 한명이라도 있다면, 진실을 아는 사람이 속한 집합(부모)를 set()에 넣어주고, 파티에 참석한 사람들이 속한 집합을 for문을 돌며 하나씩 확인해준다. 만약..

https://www.acmicpc.net/problem/17352

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 브루트포스를 이용하여 모든 경우의 수를 다 살펴봐야 하는 문제이다. 처음에는 greedy, 혹은 bfs로 푸는 방법을 생각했는데 그냥 치킨집 위치와 집 위치를 각각 저장한 뒤, 치킨집 조합을 기준으로 집 위치를 모두 탐색하며 맨해튼 거리를 갱신해주면 되는 문제였다. 어렵게 생각하면 정말 어려운 문제다.. 조합은 itertools로도 만들 수 있으나, 재귀 연습을 위해 재귀로 ..