전체 글
-
BOJ 1613 역사(Python 3)알고리즘/BOJ 2019. 2. 23. 22:02
https://www.acmicpc.net/problem/1613 플로이드 와샬 알고리즘은 단 4줄이기 때문에 외우기 굉장히 쉽다.for k for i for j , ij, ikj 이렇게만 외우면 끝 플로이드를 돌린 후서로 다른 두 사건의 번호가 주어질 때(만약 a,b라고 주어질 때) D[a][b] != INF 이면 -1D[b][a] != INF 이면 1D[a][b] == INF 이면 0을 출력하면 된다. Python으로 제출하면 시간 초과가 나기 때문에 Pypy로 제출 해야 한다. 코드 확인 123456789101112131415n,m=map(int,input().split())Max=float('inf')S=[[Max]*(n+1) for _ in range(n+1)]for i in range(m): ..
-
-
BOJ 16562 친구비(Python 3)알고리즘/BOJ 2019. 2. 20. 14:18
https://www.acmicpc.net/problem/16562 유니온 파인드를 공부하다가 정리할 필요가 있어서 글을 쓰게 되었다. 내 풀이 방법은 v,w의 값을 입력 받을 때 v의 친구비가 더 높으면 v의 루트를 w의 루트로 해두고, w의 친구비가 더 높으면 w의 루트를 v의 루트로 해두었다. 이렇게 해두면 1차적으로 값들이 끼리끼리 모이게 되고, 이 상태에서 for문을 이용해 각 학생의 루트를 다시 구해준다. 이러면 어떤 학생한테 돈을 줘야하는지 알 수 있으니 ans에 값을 더하면 된다. 코드 확인 12345678910111213141516171819202122232425def Find(x): if x==P[x]:return x P[x]=f(P[x]) return P[x]n,m,k=map(int,..
-
BOJ 16946 벽 부수고 이동하기 4(Python 3)알고리즘/BOJ 2019. 2. 18. 01:20
https://www.acmicpc.net/problem/16946 플러드 필 + BFS 문제이다.일단 먼저 말해두자면 (x, y)좌표가 1일 때마다 bfs를 돌리면 시간 초과가 나온다. 그래서 0끼리 뭉쳐있는 곳끼리 값을 설정 해줘야 한다.다 설정했으면 그때 for문을 다시 돌려 벽이 있는 곳이 나온다면 리스트를 하나 만든다음, 상하좌우에 0이 있다면 플러드필을 이용해 저장한 값을 리스트에 저장해준다.그다음 set을 이용해 중복 제거 해주고 값을 더해주면 끝난다. 코드가 너무 길어서 메인 코드 가독성을 해치기 때문에 따로 함수 2개를 구현하였다.bfs 함수는 0끼리 뭉쳐있는 곳을 묶어준 후 리스트에 넓이를 저장해주는 함수이고, Sum 함수는 플러드 필을 다하고 벽 좌표에 출력할 값을 구하는 함수이다. ..
-
BOJ 16933 벽 부수고 이동하기 3(Python 3)알고리즘/BOJ 2019. 2. 18. 01:02
https://www.acmicpc.net/problem/16933 밤에만 벽을 부술 수 있는 점에 주의하면 됩니다.파이썬은 heapq로 하면 시간 초과가 나옵니다.deque를 이용해서 다익스트라 비슷하게 풀면 됩니다. 큐에 5개의 값을 넣어주는데 n, m, k, S[n][m][k], 낮/밤 입니다.Python3으로 제출하면 시간 초과가 나오니 Pypy3으로 제출하면 됩니다. 코드 확인 1234567891011121314151617181920212223242526from collections import dequeinput=__import__('sys').stdin.readlinen,m,k=map(int,input().split())D=[input() for _ in range(n)]q=deque([(0..
-
BOJ 14442 벽 부수고 이동하기 2(Python 3)알고리즘/BOJ 2019. 2. 18. 00:50
https://www.acmicpc.net/problem/14442 벽 부수고 이동하기 1 과 다른 점은 배열 설정 말고는 없다.dist[n][m][2]를 dist[n][m][k] 로 바꿔서 풀면 된다.Python 3으로 제출하면 느리기 때문에 Pypy 3으로 제출해야한다. 코드 확인 1234567891011121314151617181920212223from collections import dequen,m,k=map(int,input().split())D=[list(map(int,[*input()])) for _ in range(n)]S=[[[-1]*(k+1) for _ in range(m)] for __ in range(n)]S[0][0][0]=1q=deque([(0,0,0)])dx,dy=[0,0,1..
-
BOJ 2206 벽 부수고 이동하기(Python 3)알고리즘/BOJ 2019. 2. 18. 00:45
https://www.acmicpc.net/problem/2206 단순 BFS문제이다.배열을 3차원 배열 dist[n][m][2]로 만들어 주면 풀기 쉽다.마지막 [2]는 벽을 부숴본 적이 없을 때/벽을 부숴본 적이 있을 때로 나눈 것이다. 코드 확인 12345678910111213141516171819202122from collections import dequen,m=map(int,input().split())S=[list(map(int,[*input()])) for k in range(n)]D= [[[-1]*2 for j in range(m)] for i in range(n)]D[0][0][0]=1q=deque()q.append((0,0,0))dx,dy=[0,0,1,-1],[1,-1,0,0]whil..
-
BOJ 10217 KCM Travel(Python 3)알고리즘/BOJ 2019. 2. 17. 01:33
https://www.acmicpc.net/problem/10217 총 24번 제출을 하였다... (통과하기전)(C언어로 통과했을 때)(파이썬으로 통과했을 때) 파이썬으로 다익스트라+DP를 구현하는데 자꾸 시간 초과,메모리 초과,틀렸습니다가 떴다. 12345678910111213141516171819202122from heapq import *input=__import__('sys').stdin.readlinefor __ in range(int(input())): n,m,k=map(int,input().split()) D=[[] for _ in range(n+1)] for i in range(k): u,v,c,d=map(int,input().split()) D[u].append((v,c,d)) S=[[f..