[Coding Test]

[백준] 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..

[백준] 4963 파이썬(python) : 섬의 개수 - (방향벡터, 대각선)

4963번: 섬의 개수 import sys sys.setrecursionlimit(10**5) def dfs(x, y): dx = [ -1, 1, 0, 0, -1, -1, 1, 1 ] #1 dy = [ 0, 0, -1, 1, -1, 1, -1, 1 ] for i in range(8): nx = x + dx[i] ny = y + dy[i] if 0

[백준] 1325 파이썬(python) : 효율적인 해킹 - (★)

1325번: 효율적인 해킹   pypy3로 제출하면 정답처리가 됩니다.  from collections import dequeimport sysn, m = map(int, sys.stdin.readline().split())graph = [ [] for _ in range(n+1) ]for _ in range(m): a, b = map(int, sys.stdin.readline().split()) graph[b].append(a) #1ans = []def bfs(v, visit): q = deque([v]) count = 0 while q: x = q.popleft() for nx in graph[x]: if not visit[nx]..

[백준] 11404 파이썬(python) : 플로이드

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) INF = (1e9) graph = [ [INF] *(n+1) for _ in range(n+1) ] for i in range(1, n+1): for j in range(1, n+1): if i == j: graph[i][j] = 0 for i in range(m): s..