1. 문제 출처 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 2. 풀이 bfs(너비 우선 탐색)를 이용하여 구하였다. 제일 어려웠던점은 아이러니하게 알고리즘 구현이 아닌 시간 초과 문제 였다.처음에는 deque 대신 리스트에 pop()을 하는 형식으로 구현 하였으나 시간 초과가 발생하였다. 이를 deque 자료형을 불러와 popleft 를 대신 사용 하였더니 해결되었다..
1. 문제 출처 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이 크게는 브루트 포스를 이용하여 모든 경우의 수를 구한 다음에 가장 결과가 큰값을 출력한다. 문제는 벽을 세우는 과정인데 이는 dfs ,bfs 2가지로 해결 할 수 있다. (시간이 오래 걸리므로 python3가 아닌 pypy3 로 실행해야 시간 초과가 되지 않는다.) bfs import copy from collections import deque # 움직이는 방향 dy = [0,0,..
1. 문제 출처 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 2. 풀이 # 테스트 테이스의 개수 t = int(input()) # 편의점 좌표 입력받는 함수 get_coordinate = (lambda : list(map(int,input().split())) ) # 길이 구하는 함수 get_legth = (lambda start , end : abs(start[0]-end[0])+abs(start[1]-end[1])) # 결과 저장하..
1. 문제 출처 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 2. 풀이 # 테스트 케이스 개수 받기 test_case_num = int(input()) # 나이트 8방향으로 이동 시 바뀌는 좌표 크기 # 원점이 좌측 상단 꼭지점이고 오른쪽, 아래쪽으로 갈 때 마다 # 1 씩 좌표가 늘어나고 그 반대는 1씩 줄어 든다 # x좌표 변화량 리스트 # x 좌표 변화량 리스트가 4인 이유는 # 원래 [-2,-1,1,2,-2,-1,1,2] 인데 -2,-..
