목록Python (4)
세상의 모든 알고리즘
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 리스트 BFS문제를 풀다 그래프 탐색문제를 풀었습니다. 핵심은 양방향 그래프 아래 부분이라고 생각합니다. graph[a].append(b) graph[b].append(a) 알고있다면 굉장히 쉬운데 모르면 이해하기 힘든.. 몇번 활용해보고 이해하시길 바라겠습니다 import sys from collections import deque input = sys.stdin.readline n = int(inp..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 전형적인 탐색문제로 DFS와 BFS 중 BFS로 문제를 풀어 보았습니다. ''' 7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 ''' import sys from collections import deque input = sys.stdin.readline numbering = [] result = [] n = int(input()) for _..
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 from collections import deque import sys input = sys.stdin.readline n,m,k,x = map(int,input().split()) graph = [[] for _ in range(n+1)] visited = [-1] * (n+1) visited[x] = 0 for _ in..
page 152 미로 탈출 BFS 문제 리스트를 입력받아 0인 괴물을 피해 n,m 좌표로 이동하는데 최소비용을 출력하기 길찾기문제는 BFS로 푸는것이 효율적이기에 BFS풀게되었고 1일때 지나갈수있는벽 0일때 못지나가는 괴물 이 두가지 조건을 조건문으로 잘 걸러내면 쉽게 풀 수 있는 문제 였습니다. from collections import deque n,m = map(int, input().split()) maze = [] for _ in range(n): maze.append(list(map(int,input()))) dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(x,y): q = deque() q.append((x,y)) while q: a,b = q.popleft() for..