Algorithm & Problem Solving/그래프 이론(DFS & BFS)
-
[백준 1194] 달이 차오른다, 가자. (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 2. 10. 13:53
www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제풀이 N, M, board : 입력값 check : 특정 key를 가지고 방문 여부 체크 비트마스크를 이용한 BFS 문제였다. 평상시 비트마스크를 싫어하였는데 이 문제를 통해 조금은 친해(?)진 것 같다... 비트마스크를 활용한 풀이에 대한 설명은 아래 참고한 코드 URL 에 자세히 설명되어 있다. 1. '0' 부터 BFS 탐색 - 새롭게 이동할 곳이 '1' 이거나 '.' 이면..
-
[백준 15686] 치킨 배달 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 30. 00:44
www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제풀이 N, M, board : 입력값 chicken : 치킨집 좌표 리스트 tmp_board : 치킨집이 없는 board (집과 빈 공간만 있는 2차원 리스트) dist : 치킨집을 기준으로 최단 이동 거리 Combination(조합) 으로 치킨집을 M개 선택하여 BFS를 통해 각 집까지의 거리를 탐색하는 방식으로 해결할 수 있다. 1. Combination을 통해 M개의 치킨집 선택하..
-
[백준 1939] 중량제한 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 27. 19:31
www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 문제풀이 N, M : 입력값 adj_list : 섬간 인접리스트 start, end : 공장이 위치한 섬의 번호 mx, mn : 이분 탐색 범위 BFS와 이분 탐색을 활용한 문제였다. 처음 접해보는 유형이었고, 새로운 방식의 아이디어 및 풀이를 얻을 수 있는 문제였다. 1. 이분 탐색을 통해 가능한 중량을 찾는다. - BFS 탐색을 통해 start 섬에서 end ..
-
[백준 2589] 보물섬 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 25. 11:48
www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제풀이 N, M, board : 입력값 check : 특정 노드 방문 여부 dist : 특정 노드까지의 거리 q : BFS를 위한 deque 모든 육지에 대해서 BFS를 통해 갈 수 있는 최대 거리를 구해주면 쉽게 해결할 수 있다. 1. 특정 좌표가 육지라면 BFS 시작한다 - 해당 위치에서 상하좌우 중 육지이면서 아직 방문하지 않았다면 방문 2. 모든 육지에 대해 1의 과정을 반복한다 코드 import sys ..
-
[백준 11559] Puyo Puyo (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 22. 01:27
www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 문제풀이 BFS를 이용한 구현문제이다. 주어진 조건만 잘 구현하면 쉽게 해결할 수 있다. 1. 뿌요 탐색 및 뿌요 부수기 - 현재 위치에서 동일한 색상의 뿌요가 4개 이상일 경우 뿌요를 부신다. 2. 1의 과정에서 없앤 뿌요가 있으면 뿌요를 내려준다. - 없앤 뿌요가 없으면 더 이상 진행할 것이 없으므로 결과를 바로 출력한다. 코드 보면 쉽게(?) 이해할 수 있다. 코드 import s..
-
[백준 16947] 서울 지하철 2호선 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2021. 1. 20. 17:07
www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 문제풀이 N : 입력값 adj_list : 양뱡향 인접리스트 check : 노드 방문 여부 체크 dist : 최소 방문 거리 DFS를 통해 사이클을 찾고, BFS를 통해 특정 노드에서 사이클 까지의 거리를 계산하는 방식으로 해결할 수 있다. check를 통해 방문한 노드(check[x] = 1), 방문하지 않은 노드(check[x] = 0), 사이클에 속한 노드(check[x] = 2..
-
[백준 14226] 이모티콘 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2020. 12. 15. 12:15
www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제풀이 S : 입력값 dp : 화면과 클립보드를 표현할 2차원 리스트, dp[i][j] = x : 화면에 있는 이모티콘의 갯수 i개, 클립보드에 있는 이모티콘의 갯수j개 일때 걸린 시간 x초 q : i, j 를 BFS로 탐색하는 deque ans : 결과값 1. BFS를 이용해 세 가지 경우를 탐색하여 deque에 넣어준다. (이때 각 연산은 1초가 소요) - 화면에 있는 i개의 이모티콘을 클립보드에 붙이는 경..
-
[백준 14502] 연구소 (Python)Algorithm & Problem Solving/그래프 이론(DFS & BFS) 2020. 11. 28. 19:58
www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 N, M, board : 입력값 virus : 바이러스 좌표 (x, y) ans : 결과값(최대 빈 공간) tmp_board : 원본 board를 훼손하지 않기 위해 복사 q : 바이러스 bfs를 위한 deque bfs(board, virus) : 바이러스를 퍼트리기 위해 bfs로 탐색 다소 비효율적이긴 하지만 6중 for문을 통해 3개의 벽을 세우는 것을 구현하였다. 1. 3개의 서로 다른 벽 세우기 구현 6중..