mondegreen

연결되어 있는 좌표의 수를 모두 더하는 문제였고 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..

너비우선탐색 개념 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문했던 정점을 시작점으로 하여 그 시작점과 인접한 정점을 다시 차례로 방문하는 방식을 말한다. 이 때 방문했던 인접 정점도 순서대로 다시 인접 정점을 탐색해야 하므로 선입선출 형태의 자료구조인 Queue(큐)를 활용한다. 방문 여부 검사를 통해 무한루프에 빠지지 말아야 한다. 너비우선탐색 특징 1) 시작 노드로부터 단계적으로 거리에 따라 탐색한다. 2) 재귀적으로 작동하지 않는다. 3) 프림 및 다익스트라 알고리즘과 유사하다. 구현 방식1) 인접행렬 두 정점이 연결되어 있는 여부를 한 눈에 확인 가능하나, 시간도 많이 사용하고 메모리 낭비가 심하다. 들어오고 나가는 간선이 한 눈에 보이기 때문에 간선이 많을 때(밀집 그래프)..