Python/백준
1504_특정한 최단경로
https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 알고리즘을 통해 저번에 최단경로를 구했었는데 이를 활용해서 풀었다. 결국 v1,v2 두개의 점을 통과하여 통과하려면 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 두가지 방법이 존재한다. 즉, 1,v1,v2 에서 다른 점들로의 최단거리를 구해놓은 배열을 하나 만들고, 위 방법에 따라서 최단거리를 정해주면 된다. impor..
1753_최단경로
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 처음에 문제를 접하고 나서 든 생각은 graph를 하나두고 시작점을 기준으로 한 배열을 하나두고 그 배열을 채워나가면 될 것 같았다. 이때 시작점을 기준으로 한배열의 경우 0번째 index는 시작점 --- 0 번 노드 사이의 간격 1번째 idnex는 시작점 --- 1 번 노드 사이의 간격 식으로 채울 생각이었다. import sys from collection..
1707_이분그래프
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이전에 그래프를 사용했다면 응용해서 풀면 된다. 결국 말은 어렵지만, 단순하게 생각해보자. 1,2,3번 3개의 점만 있다고 생각해보고 우리는 이를 빨강팀과 파랑팀으로 나눌 것이다. 1번과 2번이 연결되어있다면 1,2번은 무조건 다른팀이어야 한다. 즉, 1번이 빨강팀이라면 2번은 파랑팀이어야 한다. 그 후에 만약 2번이 3번과 연결되어 있다면 3번은 빨강팀이 될 수 밖에없다. 이런상황에서 1번과 3..
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..
2206_벽부수고 이동하기
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이전 미로탐색과 거의 유사하다. 단, 벽을 만났을때 부쉈는지 안부쉈는지 체크해서 안부쉈을경우 부수게 체크하면 된다! from collections import deque n,m = map(int,input().split()) graph = [ list(map(int,input())) for _ in range(n) ] visited = [[[0,0] for _ in ran..
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 ..