BFS

[프로그래머스] - 무인도 여행

https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 풀이] bfs를 이용해 상하좌우 인접한 땅을 찾습니다. 무인도로 이루어진 숫자의 합을 ArrayList에 추가 bfs가 끝나면 ArrayList를 오름차순 정렬 시켜줍니다. ArrayList 크기가 0이면 -1을 넣어준후 리턴 시켜주면 됩니다. [java] mport java.io.BufferedReader; import java.io.IOException; import java.io.I..

[백준] 노드 사이 거리 (1240) - Java, bfs

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net [입력] 첫 번째 라인은 노드의 개수와 거리를 알고 싶은 노드의 쌍의 수가 주어진다. 두 번째 라인부터 N-1개의 줄에 노드의 쌍과 거리가 주어진다. 그 다음 라인부터는 거리를 알고 싶은 M개의 노드의 쌍이 주어진다. [문제 해결] 노드를 양방향 연결을 한다. 시작점을 큐에 넣고 방문 처리를 해준다. bfs를 돌리면서 인접 노드들의 거리를 계산해준다. 마지막 노드에 도착하면 종료한다. [Java - bfs] import java.io.Buff..

백준 촌수 계산(2644)

촌수 계산(2644) 풀이 bfs를 통해 깊이를 세주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class FastScanner { BufferedReader br; StringTokenizer st; public FastScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st..

백준 숨바꼭질(1697)

백준 숨바꼭질 풀이 bfs를 돌려서 깊이를 세어서 중복되는 위치의 수와 가장 낮은 위치를 출력해 주기만 하면되는 전형적인 그래프 문제 첫 제출은 2차원 배열을 사용해서 그런지 메모리 초과가 나왔는데 ArrayList로 해결 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static int depth[]; public static boolean visited[]; public static ArrayList map = new ArrayList(); public static int max; public sta..

프로그래머스 카카오 프렌즈 컬러링 북

프로그래머스 카카오 프렌즈 컬러링 북 풀이 bfs를 이용하여 해결 소요 시간 약 20분 class Pos{ public int x; public int y; public Pos(int y, int x){ this.y = y; this.x = x; } } class Solution { int dx[] = {0, 0, -1, 1}; // 상 하 좌 우 int dy[] = {-1, 1, 0, 0}; boolean visited[][]; PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); public int[] solution(int m, int n, int[][] picture) { int numberOfArea = 0; int maxSizeO..

프로그래머스 게임 맵 최단 거리

프로그래머스 게임 맵 최단거리 풀이 시작점을 기준으로 bfs 돌려서 큐에 넣을 때마다 이전거리 + 1씩 해줘서 넣어준다. 도착지점 거리를 리턴해준다 내가 푼 풀이 import java.util.*; class Pos{ int x; int y; public Pos(int y, int x) { this.y = y; this.x = x;} } class Solution { static int dx[] = {0, 0, -1, 1}; static int dy[] = {-1, 1, 0, 0}; static int visited[][]; public int solution(int[][] maps) { return bfs(maps,new Pos(0,0)); } public static int bfs(int[][] ma..