그래프4

• 

  프로그래머스 - 퍼즐조각 맞추기 문제 설명 한 게임판과 퍼즐조각이 흩어져있는 판이 주어진다. 게임판에 비어있는 란에 흩어져있는 판에 있는 퍼즐을 끼워 넣어 빈 공란을 채우는 개수를 구하는 문제이다. 여기서의 핵심은 퍼즐조각이 위치한 판에서 도형을 추출하는 과정이 중요하다. 그리고 이 도형을 빈 공란에 맞춰 끼울 수 있는지 여부도 판단해야 한다. 나는 해당 도형을 BFS로 추출했다. 그리고 해당 정보를 가지고 객체를 생성했다. 객체는 해당 도형을 표현한 2차원 배열을 필드변수로 가지고 있다. class Puzzle { int cnt; // 1의 개수 int map[][]; public Puzzle(int map[][], int cnt) { this.map = map; this.cnt = cnt; } } 여러 도형들을 BFS로 추출하여 해.. Algorithm/프로그래머스 2023. 4. 17.

• 

  백준 - 단절점과 단절선 문제 설명 트리가 주어졌을 떄, 해당 간선 또는 정점을 제거하여 두개 이상의 그래프로 나뉘어 질 수 있다면 “yes” 아니면 “no”를 출력하는 문제이다. 풀이 ‘간선’ 이라 함은 두 정점을 연결하는 요소로서 어느 간선을 제거하던 두 그래프의 단위로 무조건 나눌 수 있다는 것이다. 어느 한 정점을 제거했을 떄, 두 그래프 요소로 나뉠수 있는지는 루트와 단말 노드인지를 판단하면 된다. public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(reader.readLine());.. Algorithm/백준 2023. 3. 14.

• 백준 - 치즈 문제 설명 공기면과 닿은 치즈는 녹는다. 치즈가 전부 사라지는 시간과 전부 사라지기전 치즈 개수를 구하라 생각한 아이디어 공기면과 맞닿는 치즈인 것을 어떻게 판별 할 수 있을까? 문제 첫줄에 힌트 있음 - > 가장자리는 무조건 적으로 치즈가 존재하지 않음을 의미 가장 자리 부터 탐색에 1이 맞닿는 곳이면 녹을 치즈인 것을 알 수 있다. 풀이 public static int[] solution() { int[] answer = new int[2]; int cheeseCnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] == CHEESE) { cheeseCnt++; } } } int hour = 0; int lef.. Algorithm/백준 2023. 2. 12.

• 

  그래프 그래프 목차 1.그래프란 2.그래프 용어 3.그래프 구현 방법 4.그래프 종류 4.그래프 탐색 그래프란 정점과 간선으로 이루어진 자료구조. 트리는 그래프의 일종이다. 네트워크 모델이다. 객체와 이에 대한 관계를 나타낸다. 예) 지하철, 도로 등. 그래프의 순회방식 : BFS, DFS 그래프 용어 정점 : 노드로서 정점에는 데이터가 저장. 간선 : 링크라고 불리우며 노드간 관계를 나타냄. 인접 정점 : 간선에 의해 연결된 정점. 단순 경로 : 경로 중 반복적으로 탐색하는 정점이 없는 경로. 즉 같은 간선을 지나지 않는 경로. 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 : 방향 그래프에서 사용되는 용어로서 한 노드에서 외부로 향하는 간선의 수를 의미. 진출 차수 : 방향 그래프에서.. CS/DataStructure 2021. 7. 30.