본문 바로가기

Algorithm

 (130)
[Python] 백준 4963번 : 섬의 개수 (S2) #문제 www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #풀이 & 학습한 내용 유기농 배추(supremo7.tistory.com/179)와 같은 문제이나, 다른 점은 대각선으로 있는 것도 연결 된다고 보는 것입니다. 이는 dx,dy에 대각선 4방향만 추가해주면 됩니다. #소스코드 from collections import deque #bfs에서 큐 쓰기위해 dx=[0,0,1,-1, 1,-1,1,-1] dy=[1,-1,0,0, 1,-1,-1,1] #상하좌..
[Python] 백준 14502번 : 연구소 (G5) #문제 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net #풀이 & 학습한 내용 브루트포스로 서로다른 세 좌표를 구하고, 모두 0(빈칸)이면 1(벽)로 바꿔서 벽을 세운 후 dfs/bfs를 수행해야 하는 문제입니다. 이때, 서로다른 세 좌표를 itertools.combination을 이용했는데, 이 부분을 정확히 익힐 필요가 있습니다. #소스코드 import copy,sys,itertools from collections import deque #큐 쓰기위해 input=s..
[Python] 백준 11724번 : 연결 요소의 개수 (S2) #문제 www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net #풀이 & 학습한 내용 DFS 또는 BFS로 그래프를 탐색해서 연결된 요소의 개수를 구해야 합니다. 이때, dfs를 쓰려면 재귀깊이를 꼭 늘려줘야 합니다. 유기농 배추(supremo7.tistory.com/179)와 매우 유사한 문제로 풀이가 비슷합니다. #소스코드 from collections import deque #bfs에서 큐 쓰기위해..
[Python] 백준 2573번 : 빙산 (G4) - DFS&BFS 필수문제4 #문제 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net #풀이 & 학습한 내용 2차원 리스트를 실시간으로 갱신시키면서 그래프탐색을 하면 안되고, 다른 2차원 리스트를 선언후 복사붙여넣기해서 초기의 2차원 리스트를 변형시키지 않고 탐색을 진행해야 하는 문제입니다. 이때 반드시 깊은 복사를 해야되고, 이에 대한 설명은 justdoit709.tistory.com/52에 자세히 나와있습니다. #소스코드 from collections import deque #큐..
[Python] 백준 2468번 : 안전 영역 (S1) - DFS&BFS 필수문제3 #문제 www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net #풀이 & 학습한 내용 DFS 또는 BFS로 구분되는 영역의 최대 갯수를 구하는 문제입니다. #소스코드 from collections import deque #큐 사용하기 위해 dx=[0,0,1,-1] dy=[1,-1,0,0] #상하좌우 def bfs(q): #bfs로 경로있는 vertex들 모두 방문처리 while q: v=q.popleft() now_x=v[0] now_y=v[1] #큐에서 뽑은 vertex..
[Python] 백준 5014번 : 스타트링크 (G5) - DFS&BFS 필수문제2 #문제 www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net #풀이 & 학습한 내용 현재 층수에서 목표 층수까지 이동하는 최소 횟수를 구하는 문제입니다. 가중치가 없으므로 최단경로를 bfs를 통해 구해줍니다. #소스코드 from collections import deque def bfs(q): while q: v=q.popleft() now_floor=v[0] #큐에서 뽑은 현재 층 now_count=v[1] #현재 층까지의 이동횟수 if now_floor==find_floo..
[Python] 백준 2644번 : 촌수계산 (S2) - DFS&BFS 필수문제1 #문제 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net #풀이 & 학습한 내용 인접리스트로 그래프를 저장한 뒤에, 출발점에서 도착점까지의 최단경로를 계산하는 문제입니다. 가중치 없는 간선을 가진 최단경로는 bfs를 이용하면 됩니다. #소스코드 from collections import deque #큐 사용하기 위해 def bfs(q): while q: v=q.popleft() now_v=v[0] #현재의 vertex count=v[1] #현재의..
[Python] 백준 1707번 : 이분 그래프 (G4) - DFS&BFS단계별11 #문제 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net #풀이 & 학습한 내용 "그래프 순회를 통해 이분 그래프를 판별하는 문제"입니다. 이분 그래프를 판정하는 방법으로 인접한 vertex가 서로 다른 두 가지 색으로만 그래프가 칠해진다는 점을 이용하면 됩니다. 이때, 그래프가 연결 그래프라는 조건이 없으므로, disconnected graph에 대해서도 고려하며 문제를 풀어야 합니다. input()을 쓰면 PyPy3에서는 통과되지만 Python..

티스토리툴바