전체 글
-
[DFS/BFS] 문제 이름 : 미로 탈출Algorithm/유형별 문제 풀기 2021. 7. 8. 11:34
문제 설명 N x M 크기의 직사각형의 미로가 주어질 때, 주인공의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸식 이동할 수 있다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시되는데, 이때 주인공이 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 1. 사용 알고리즘 그래프 탐색 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 2. 문제 해결 아이디어 주어진 문제는 미로를 탈출하기 위한 최소 칸의 개수를 구하는 것이므로, 탐색 시 더 이상 길이 없다면 다시 되돌아오게 되고 그러면 이때까지 잘못된 길로 갔을 때의 이동횟수..
-
[DFS/BFS] 문제이름 : 음료수 얼려 먹기Algorithm/유형별 문제 풀기 2021. 7. 5. 11:59
문제 설명 N X M 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상 하 좌 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 1. 사용 알고리즘 그래프 탐색 - BFS & DFS 2. 문제 해결 아이디어 주어진 좌표의 위치와 해당 위치의 상하좌우에 대해 구멍이 뚫려서 연결되어 있는지 탐색하면 된다. 이때 주어진 2차원 배열을 그래프 형태로 생각하면, DFS와 BFS 알고리즘을 적용해 해결할 수 있다. 3. 코드 구현방식1) BFS(너비 우선 탐색)를 사용해 가까운 좌표부터 확인하기 각 좌표가 상하좌우에 대해 움직일 수 있는 ..
-
[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..