백준
10217_KCM Travel
https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 되게 어려운 문제였다.. 처음에는 시간을 최소로 하는 알고리즘을 찾으며 비용의 제약을 두는방식으로 하면 될것 같았으나, 생각을 해보니 당장은 시간도 비용도 손해같지만 결국 초반에 돌아가야하는 경우가 생겼다. 1 6 149 8 1 2 60 20 2 3 30 70 1 3 100 80 1 3 20 180 3 4 20 100 3 5 150 20 5 6 50 40 4 ..
11404_플로이드
https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해당 문제역시 이전에 풀었던 방법을 그대로 적용해보았더니 잘 풀렸다 ㅎㅎ 최단경로를 구하는 문제나 미확인 도착지를 한번 보고 오는걸 추천한다! import sys import heapq input = sys.stdin.readline INF = int(1e9) n = int(input()) m = int(input()) graph = [ [] for _ in range(n+1)] for _ in ..
7562_나이트의 이동
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 역시 bfs를 이용한 문제이다! 이전에 풀었던 문제들과 유형이 같다. dx,dy가 기존에 상,하,좌,우였던 것을 나이트의 이동에 맞춰서 바꿔주기만 하면 쉽게 풀 수 있다. import sys from collections import deque input = sys.stdin.readline t = int(input()) dx = [-2,-1,1,2,2,1,-1,-2] dy = [1,2,2,1,-1..
1697_숨바꼭질
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net bfs를 이용하면 풀면 된다! 처음엔 단순하게 que에 현재 점을 추가해 가면서 하려 했는데 수가 너무 커지거나 해서 시간초과나 메모리 초과가 계속해서 났다. 한번 들렀던 점은 그때가 최소이기에 두번 들리지 않고, 또한 값이 0 < x < 100000으로 정해져 있기때문에 이를 제한해두고 문제를 푸니 풀렸다. from collections import deque n,m ..
1012_유기농 배추
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이전 문제와 똑같은 유기농 배추 문제이다. 역시 이차원 그래프, visited배열, 밭의 지도를 그리고 이어져있는 밭의 개수를 새면 된다. t = int(input()) dx = [0,1,0,-1] dy = [1,0,-1,0] for _ in range(t): m,n,k = map(int,input().split()) farm = [ [ 0 for _ in range(m) ] for __ in range(n)..
2606_바이러스
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이전글에서 사용한 bfs를 활용해서 풀어봤다. 어차피 연결된 모든 노드를 다 돌아야하기 때문에 bfs가 더 효율적일것이라 생각해봤다. 문제를 해결한 후에 검색해보니 실제로 두 방식의 차이는 크게 없다고 한다 ㅎㅎ.. 좀 더 공부하니 이렇게 모든 경우를 탐색해야하는경우는 dfs가 약간 더 빠르다고 하니 알아두면 좋을 것 같다. from collections import deque c = int(input..