본문 바로가기

전체 글

 (263)
[백준] 2644 : 촌수계산 python 전에 풀었던 케빈 베이컨의 6단계 법칙 문제에서 사용했던 방법을 그대로 썼다. 모든 정점에 대해 bfs를 수행할 필요는 없고, 촌수를 계산해야 하는 번호에 대해서만 bfs를 수행해주면 된다. import sys from collections import deque input = sys.stdin.readline n = int(input()) a,b=map(int,input().split()) m=int(input()) graph = [[]for i in range(n+1)] result = [] for i in range(m): s,e = map(int,input().split()) graph[s].append(e) graph[e].append(s) def bfs(start): visited = [Fal..
[백준] 1389 : 케빈 베이컨의 6단계 법칙 python n개의 정점에 대해 bfs를 수행할 때마다 num이라는 배열에 연관된 정점사이의 거리를 기록하고, num의 총합을 result라는 리스트에 append해준다. 1-3, 3-2, 2-4, 4-5이렇게 연결되어있을 때 1번을 시작 정점으로 bfs를 수행하면서 1번의 인접정점인 3,4의 거리가 1이라는 것을 num[3], num[4]에 기록해준다. 그리고 3번을 시작 정점으로 다시 bfs를 수행할 때 3번의 인접 정점인 2번자리 num[2]에는 num[3]+1을 저장하는 방식으로 하면 1번과 연관이 있는 각 정점간의 거리를 알 수 있다. import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().split()..
[백준] 2606 : 바이러스 python 1번 컴퓨터와 자기 사이에 아무리 많은 컴퓨터가 있더라도 연결되어있다면 무조건 바이러스에 걸린다. 따라서 1번 노드에서 BFS를 수행하면서 1번과 연결된 컴퓨터의 개수를 세주면 된다. 1. 컴퓨터의 수 n을 입력받는다. 2. 간선의 수 m을 입력받는다. 3. m줄에 걸쳐 그래프의 연결 정보를 입력받고 graph라는 2차원 리스트에 저장한다. 4. 해당 정점을 방문했는지 확인하는 visited 리스트를 만들고 0으로 초기화한다. 방문할 때마다 1로 바꿔주면, BFS를 수행한 뒤에 visited 리스트의 총합-1을 했을 때 1번과 연결된 컴퓨터의 개수를 알 수 있다. 5. dfs 함수를 작성한다. 6. 1번 컴퓨터에서 dfs함수를 수행하고 연결된 컴퓨터의 개수를 출력한다. import sys input = ..
[백준] 2178 : 미로 탐색 python BFS를 수행하면서 각 위치마다 거리를 적어두는 식으로 해결하면 되는 문제다. from collections import deque n,m = map(int,input().split()) graph = [[]for i in range(n)] for i in range(n): data = input() for c in data[:]: graph[i].append(int(c)) dx = [-1,1,0,0] dy = [0,0,-1,1] def bfs(x,y): queue = deque() queue.append((x,y)) while queue: x,y = queue.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] if nx=m: continue if grap..
[백준] 1260 : DFS와 BFS python 제목 그대로 DFS와 BFS를 수행한 결과를 출력하면 되는 문제인데, 인접정점이 오름차순으로 입력되지 않기 때문에 입력을 받은 후에 정렬을 한 번 해줘야 한다. from collections import deque n,m,v = map(int,input().split()) graph = [[]for i in range(n+1)] visited = [False]*(n+1) for i in range(m): s,e = map(int,input().split()) graph[s].append(e) graph[e].append(s) for i in range(n+1): graph[i].sort() def dfs(graph, v, visited): visited[v] = True print(v,end=' ') f..
[백준] 2798 : 블랙잭 python n,m = map(int,input().split()) data = list(map(int,input().split())) res = 0 tmp = 0 for i in range(n-2): for j in range(i+1,n-1): for k in range(j+1,n): tmp = data[i]+data[j]+data[k] if tmp>=res and tmp
[백준] 11286 : 절댓값 힙 python 이전에 풀었던 최댓값 힙 문제에서 최대 힙을 만들기 위해 아래와 같은 방식으로 힙에 숫자를 추가했었다. heapq.heappush(h,(-item,item)) 이렇게 튜플 형식으로 값을 추가하면 튜플의 첫 번째 원소인 -item의 오름차순으로 정렬되기 때문인데, 이 문제에서는 절댓값의 오름차순으로 정렬을 해야 하니 heapq.heappush(h,(절댓값,원래값))의 형식으로 값을 추가하면 되겠다는 생각이 들었다. 1. n을 입력받는다. 2. 우선순위 큐가 될 리스트 h를 생성한다. 3. n번에 걸쳐 x를 입력받는다. 3-1. x가 0일 때 3-1-1. h에 아무것도 없으면 0을 출력한다. 3-1-2. 절댓값이 가장 작은 값을 출력하고 제거한다. 3-2. x가 0이 아니면 우선순위 큐에 (abs(x),x)..
[백준] 13305 : 주유소 python 저렴한 기름값으로 최대한 멀리 가야 하는 문제이다. 일단 현재 도시의 기름값으로 다음 도시까지 가는 데에 필요한 기름을 사고, 다음 도시의 기름값이 더 저렴할 때에만 기름값을 업데이트하면 된다. 1. n을 입력받는다. 2. 다음 도시까지의 거리를 순서대로 dist라는 list에 저장한다. 3. 각 도시의 기름값을 oil이라는 list에 저장한다. 4. 현재 기름가격인 price에 첫 번째 도시의 기름값(oil[0])을 저장한다. 5. 총 금액인 total을 0으로 초기화한다. 6. 1번 인덱스부터 총 금액에 기름값과 다음 도시까지의 거리를 곱한 값을 더한다. 7. 만약 다음 기름값이 더 싸다면 price를 업데이트 한다. n=int(input()) dist = list(map(int,input().spl..

티스토리툴바