[Coding Test]/[백준]

[백준] 16236 파이썬(python) : 아기 상어 - (★)

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net import sys from collections import deque n = int(sys.stdin.readline()) graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ] shark_size = 2 #1 eat_cnt = 0 #2 fish_cnt = 0 #3 time = 0 #4 dx = [ 0, 0,..

[백준] 2644 파이썬(python) : 촌수계산 - (visit과 cnt의 차이)

2644번: 촌수계산 import sys from collections import deque n = int(sys.stdin.readline()) a, b = map(int, sys.stdin.readline().split()) m = int(sys.stdin.readline()) graph = [ [] for _ in range(n+1) ] for _ in range(m): x, y = map(int, sys.stdin.readline().split()) graph[x].append(y) graph[y].append(x) visit = [0]*(n+1) #1 def bfs(): q = deque() q.append(a) while q: x = q.popleft() if x == b: return vi..

[백준] 2573 파이썬(python) : 빙산 - (★)

2573번: 빙산  import sysfrom collections import dequen, m = map(int, sys.stdin.readline().split())graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n)]dx = [ 0, 0, -1, 1 ]dy = [ -1, 1, 0, 0 ]year = 0check = Falseq = deque()def bfs(x, y): q.append((x, y)) while q: x, y = q.popleft() visit[x][y] = True for i in range(4): nx = x + dx[i] ..

[백준] 1926 파이썬(python) : 그림 - (DFS 메모리초과(방향벡터x))

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net DFS로 제출하면 메모리초과가 발생하는 문제다. 너무 자주 틀려서 블로그의 다른 코드를 읽지도 않고 이것도 틀릴까?해서 넣었는데 그것들도 틀렸다. 단념하고 BFS로 바꿀까 하다가 DFS로 풀어도 통과하는 코드를 찾을 수 있어서 그 분의 코드를 참고했다. 방향벡터와 방문처리 리스트 visit을 삭제해줘야 메모리초과가 발생하지 않는다. import sys from collections import dequ..

[백준] 1504 파이썬(python) : 특정한 최단 경로 - 다익스트라

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 특정노드를 반드시 지나서 가야하는 다익스트라 알고리즘 문제이다. 이전 문제(1916)에서 조건이 추가된 문제. https://hgk5722.tistory.com/179 [백준] 1916 파이썬(python) : 최소비용 구하기 - 다익스트라 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 ..

[백준] 1916 파이썬(python) : 최소비용 구하기 - 다익스트라

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import heapq import sys n = int(input()) m = int(input()) INF = int(1e9) #1 graph = [ [] for _ in range(n+1) ] visit = [INF] *(n+1) for i in range(m): a, b, c = map(int, sys.stdin.readline().split()) grap..