개발조아

문제 링크 : https://www.acmicpc.net/problem/22944 22944번: 죽음의 비 가로, 세로 길이가 $N$인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지 www.acmicpc.net 나는 BFS로 풀었고 방문체크는 해당 칸을 방문했을 때의 체력을 기록했다. 그래서 다음번에 다시 방문했을 때 해당 칸보다 체력이 높아야 이동이 가능하게 했다. 더 낮은데 해당 칸으로 이동해봐야 기존의 방문했을 때보다 적게 가기 때문이다. BFS 진행시 범위 안에 들어왔을 때 조건들을 체크한다. 만약 E점이라면 종료한다. 아니라면 다음 점이 우산이라면 현재 내구도를 d로 바꾼다. ..

문제 링크 : https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 건물의 개수가 최대 100개고 모든 건물사이의 최단 거리를 구해놓으면 쉬우므로 플로이드 와샬로 해결하였다. 입력으로 반은 건물로 배열을 구성하는데 가중치는 1로 넣자 그리고 플로이드 와샬로 각점에 대해서 최단거리를 구해 놓자. 다음 치킨집을 지으려는 매장 두곳을 골라야한다. 이중포문으로 골라도 되지만 귀찮으니 combinations을 사용했다. 두개의 ..

문제 링크 : https://www.acmicpc.net/problem/22868 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net 짧은 경로가 사전순으로 먼저 나온것이 우선으로 되어야한다고 해서 입력으로 생성한 인접 리스트를 정렬해주고 시작했다. 일단 나는 두번의 BFS를 수행했다. S에서 E로, E에서 S로 BFS를 두번 진행한다. S에서 E로 진행할 때는 경로를 저장한다. 방문체크 할때 다음 점이 어느 점에서 왔는지 넣어 준다. 그리고 도착했을 때는 마지막 점에서 거꾸로 올라..

문제 링크 : https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 각각의 샘터에서 좌우로 집을 하나씩 집을 놔보고, 그리고 그 집 양옆으로 집을 하나씩 놔보면 결국 불행도가 최소로 되게 집이 위치하게 된다. 그래서 큐에 집의 좌표를 넣고 집이 k개가 될 때 까지 수행해주면 된다. 결국 BFS를 수행하면 된다. 문제는 범위이다. 샘터는 -1억에서+1억까지다. 거기까지이고 집까지 놀 위치를 고려한다면 2억개가 넘는다. 따..

문제 링크 : https://www.acmicpc.net/problem/22860 22860번: 폴더 정리 (small) main 폴더 하위에는 FolderA 폴더 하위에 있는 File1, File2, FolderB 폴더 하위에 있는 File1, File3이 있다. 파일의 종류는 File1, File2, File3 총 3가지이고, 파일의 총 개수는 File1, File2, File1, File3 총 4개이다. mai www.acmicpc.net 그냥 트리 구조 만들어서 했다. 노드는 이름, 종류, 파일 리스트, 폴더 리스트 4가지로 구성했다. 그리고 folders라는 딕셔너리에 입력으로 주어지는 폴더 정보의 상위 폴더 노드를 저장했다. main FolderA 1 FolderA File1 0 위의 두개 입..

문제 링크 : https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 평범한 BFS 문제이다. N이 최대 1000이므로 그래프 좌표를 인접 리스트로 하자. from sys import stdin from collections import deque input = stdin.readline s,e = map(int, input().split()) n,m = map(int, input().split()) adj..

문제 링크 : https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 역이랑 하이퍼튜브를 어떻게 표현할까를 고민했던 문제이다. 나는 각 역에 연결된 하이퍼튜브의 번호 배열, 각 하이퍼튜브가 연결한 역의 번호 두가지를 사용했으며 각각은 인접리스트로 했다. 입력 순서대로 하이퍼 튜브에 0번부터 번호를 매겨서 저장했다. 설명하면 아래와 같다. 하이퍼 튜브가 1 2 3 1 4 5 라고 들어 왔다고 해보자. 각 역에 연결된 하이퍼튜브..

문제 링크 : https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 처음에 문제 조건을 잘못이해해서 틀렸었다. 나는 a-b, b-c라면 a-c도 친구라고 이해하고 풀었더니 63%였나 그쯤에서 틀렸다고 나왔다. 그래서 예제를 찾아보고 돌려보니 a-b, b-c라면 a-c라는 관계도 있어야한다. 즉 모든 친구가 서로서로 모두 친구사이어야한다. 건너서 친구면 친구가 아닌 것이다. 우선 나는 BFS로 풀었다. 사용하는 자료구조는 우선순위큐와 인접행렬, 인접리스트를..