그래프
-
[BFS] 문제 이름 : Reach the End in TimeAlgorithm/HackerRank 2021. 7. 20. 11:27
문제 설명 2-D grid가 주어졌을 때 상단의 가장 왼쪽 코너에서부터 하단의 가장 오른쪽 코너까지 K초 안에 도착 가능하다면 "Yes"를, 불가능하다면 "No"를 반환해라. 막힌 곳은 '#'으로, 안막힌 곳은 '.'으로 표시된다. 시작 지점과 도착 지점은 unblocked cell이다. 상하좌우로 이동이 가능하고, 인접 cell로 이동하는데 1초가 소요된다. 사용 개념 그래프 탐색, BFS 문제 해결 아이디어 2021.07.08 - [Algorithm/유형별 문제 풀기] - [DFS/BFS] 문제 이름 : 미로 탈출 (위의 문제와 동일한 개념의 문제이다! 문제 내용만 다를 뿐 사실상 동일하다.) 주어진 문제는 시작 지점으로 부터 특정 위치(도착 지점)까지 걸리는 시간을 구하는 것이므로 탐색을 사용해야 ..
-
[DFS/BFS] 문제 이름 : 미로 탈출Algorithm/유형별 문제 풀기 2021. 7. 8. 11:34
문제 설명 N x M 크기의 직사각형의 미로가 주어질 때, 주인공의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸식 이동할 수 있다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시되는데, 이때 주인공이 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 1. 사용 알고리즘 그래프 탐색 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 2. 문제 해결 아이디어 주어진 문제는 미로를 탈출하기 위한 최소 칸의 개수를 구하는 것이므로, 탐색 시 더 이상 길이 없다면 다시 되돌아오게 되고 그러면 이때까지 잘못된 길로 갔을 때의 이동횟수..
-
[DFS/BFS] 개념정리2 - 그래프, 인접행렬, 인접리스트Algorithm/개념정리 2021. 7. 4. 11:56
그래프 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)라고도 함 두 노드가 간선으로 연결되어 있다면, '두 노드는 인접하다(Adjacent)'라고 표현함 그래프 표현 방식(2가지) 1. 인접행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 -> 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 /* * Adjacency Array(인접행렬) */ class ArrGraph{ private int[][] arrGraph; //2차원 배열 선언 //그래프 초기화 public ArrGraph(int graphSize) { //vertex가 1부터 시작할 때 this.arrGraph = new int[graphSize+1][graphSi..