개발조아

문제 링크 : 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/16719 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 나는 진행을 거꾸로했다. 완성된 문자열에서 하나씩 지워가면서 체크했다. 문자를 중간에 끼워넣고 하는 아이디어가 잘안떠올라서 그냥 거꾸로 진행했다. 처음에는 입력으로 들어온 문자열을 가지고 시작하며 정답 배열에 입력 문자열을 저장해놓자. 다음부터는 결과의 마지막 문자열을 가지고 수행한다. 우선 현재 문자열을 리스트로 바꿔서 두개의 리스트에 저장했다. 하나는 현재 기준으로 문자..

문제 링크 : 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/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net BFS로 풀었다. 처음에는 숫자는 최대 값이 1백만이고 k는 10이어서 1백만x11개의 배열을 만들어서 BFS로 풀이 했다. 큐에 쌓이는 것과 2천만크기의 배열때문에 메모리 초과가 난 것 같다. 그래서 방문 체크를 set을 사용했다. 대충 횟수 따져보자 입력이 123456이 들어오면 경우의 수는 6! 이므로 충분히 작다. 따라서 set으로 방문체크해도 충분히 통과할 수 있을 것 이다. 입력 숫자부터 각 숫자를 바꿔가면서 BFS를 진행하자. 방문 체크는 ..

문제 링크 : 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로 풀었다. 사용하는 자료구조는 우선순위큐와 인접행렬, 인접리스트를..