mondegreen

[Part2-Chapter04-Clip02]- 백준 11725 트리의 부모 찾기트리도 그래프의 일종이다. 단, 순환이 없는 그래프이다. 그래프 문제를 풀 때와 마찬가지로 인접 리스트를 선언하고 간선의 양 끝 정점을 리스트에 담아줬다. 부모를 찾는 함수를 구현하는 데 약간 어려움을 겪었다. 정점들을 연결된 순서대로 타고 가는데 루트 노드인 1부터 시작해서 따라가다 보면 직전의 정점이 즉, 나를 호출한 정점이 부모가 되는 로직이다. 이미 방문한 경우는 제외하고 자식 노드를 계속 찾아나가면서 자식 노드를 찾을 때마다 정답 배열에 부모인 직전 정점을 넣어주면 문제를 해결할 수 있다.package BaekJoon.tree;import java.util.ArrayList;import java.util.Scanner..

연결되어 있는 좌표의 수를 모두 더하는 문제였고 BFS를 구현했으며 연결되어 있는 여부를 Queue를 활용해서 해결했다. 그 외에는 경계를 벗어나거나 char 를 int로 변환해서 더해주는 것 정도 고려하면 될 것 같다. import java.util.*; class Solution { public static char[][] map; public static boolean[][] visited; public int[] solution(String[] maps) { int rLen = maps.length; // 행 int cLen = maps[0].length(); // 열 map = new char[rLen][cLen]; for(int i = 0; i

import java.util.*; class Solution { public static Deque dq; public static int dist[][]; public static int n, m; public static class Position{ int r; int c; public Position(int x, int y){ this.r = x; this.c = y; } } public int solution(int[][] maps) { int answer = -1; n = maps.length; m = maps[0].length; dist = new int[n][m]; dist[0][0] = 1; dq = new ArrayDeque(); dq.add(new Position(0, 0)); int..

그래프의 개념 - 아이템들과 이들 사이의 연결관계를 표현하는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조 - 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가진 원소들을 표현하기에 편리함 - 정점: 그래프의 구성요소로서 하나의 연결점 - 간선: 두 정점을 연결하는 선 - 차수: 정점에 연결된 간선의 수 그래프의 종류 무향 그래프 유향 그래프 가중치 그래프 사이클 없는 방향 그래프(Directed Acyclic Graph) 완전 그래프: 정점들에 대해 가능한 모든 간선을 가진 그래프 부분 그래프: 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프의 표현 1) 인접행렬: 2차원 배열 이용하여 간선 정보 저장 희소 그래프인 경우, 즉 정점 수 대비 간선 수가 ..