개발조아

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

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

문제 링크 : https://www.acmicpc.net/problem/16509 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 이동 규칙이 특이한 BFS 문제이다. 문제에 왕에 대한 규칙이 있지만 무시해도된다. 현재 점에서 상하좌우로 한칸 간후 해당 칸에서 대각으로 두칸을 이동한것이 한번의 움직임이다. 파란점이 상이 움직일 수 있는 구역이다. 그리고 움직이는 도중에 다른 말을 만나면 안된다. 왕도 해당 된다. 그리고 움직임의 끝에 왕과 만나야한다. 다시말해 위의 그림에 파란점에 왕이 있어야 만나는 것이다. 위에 그림..