BFS

📖 문제 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 💡 풀이 방식 • BFS 검 존재 여부와 함께 방문 표시 나타내는 3차원 배열 visited[x][y][2] → visited[x][y][0] : 검 없고, 방문했음 → visited[x][y][1] : 검 있고, 방문했음 (0,0)부터 (N-1, M-1)까지 BFS 탐색을 수행한다.큐에는 (현재 행 위치, 열 위치, 그람(검) 유무, 이동 시간) 4가지 값을 들고 다닌다. Queue q = new ArrayDeque(); q.add(ne..

📖 문제 14716번: 현수막 혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라. www.acmicpc.net 💡 풀이 방식 • BFS 1. 격자의 모든 칸을 입력받는다. 2. 격자의 모든 점을 돌면서, 방문한 적 없는 글자(1)인 부분에서 BFS를 수행하고, 그 수행 횟수를 구한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 import java.util.*; import j..

📖 문제 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 💡 풀이 방식 • BFS + 브루트포스 "모든 최단 거리 중 가장 긴 구간" 모든 육지(L)에서 BFS를 수행하며, 현재 육지에서 다른 위치까지의 가장 긴 시간이 걸리는 거리를 구한다. 그리고 그 거리를 정답과 비교해 더 큰 값으로 정답을 갱신한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 4..

📖 문제 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 💡 풀이 방식 • BFS w와 h가 0이 아닐 때만 아래와 같이 진행한다. 1. 격자의 값을 입력받는다.2. 모든 점을 탐색하며 방문하지 않은 땅에 대해 BFS 탐색을 실행하고, 섬 개수를 증가시킨다. - BFS 탐색: 격자 범위를 벗어나지 않고, 방문한 적 없고, 땅(1)인 값에 대해 8방향 탐색 수행 (상하좌우 + 대각선 4방향) 3. 구한 섬 개수를 출력한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

📖 문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 풀이 방식 • DFS + BFS + 브루트포스 1. 입력을 받으면서 빈 칸의 위치와 바이러스의 위치를 리스트에 저장해둔다. - 빈 칸 위치 저장한 이유 : 빈 칸 위치들 중 3개만 뽑으려고 할 때 완전탐색으로 모든 빈 칸 위치 안 찾으려고 - 바이러스 위치 저장한 이유 : 완전탐색으로 바이러스 위치 안 찾으려고 2. 빈 칸 중 3개를 뽑아 벽을 세우고, 바이러스를 퍼뜨린다. 2-1) 빈 칸 중 3개 뽑는 방법 : DFS private static void dfs(..

📖 문제 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 💡 풀이 방식 • 시뮬레이션 + BFS 1. 크기가 가장 큰 블록 그룹을 찾는다. → BFS static Block findMaxBlockGroupe() { visited = new boolean[N][N]; Block maxBlock = new Block(0, 0, EMPTY, Integer.MIN_VALUE, Integer.MIN_VALUE); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) ..

📖 문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡 풀이 방식 • BFS 인구 이동이 가능하지 않을 때까지 인구 이동을 진행한다. (while문)→ 완전탐색을 통해 격자 내의 모든 점에 대해 인구 이동이 가능한지 확인한다. (move 메소드) → 모든 점에 대해 4방향 탐색하며인접한 나라와 국경선이 열려있다면, 해당 나라에서 이동하며 연합한다. (BFS) - 이동 및 연합 가능한 나라는 방문한 적 없고, 두 나라 간 인구 수 차이가 L이상 R이하인 나라여야 한다. - 조건을 만족하는 인접..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • BFS 로봇이 있는 위치부터 BFS를 진행한다. - 큐에 로봇 위치 rx,ry와 이동 거리를 저장한다.- 만약 현재 위치가 목적지인 경우, 정답을 여태까지의 이동 거리로 설정하고 while문을 종료한다.- 목적지가 아니라면, 다음 이동할 지점을 찾는다. - 현재 지점에서 4방향 탐색을 한다. 이 때 한 방향을 정해서 해당 방향으로 최대한 끝까지 탐색을 진행한다. (while문 사용) - 진행하다가 격자 범위를 벗어나거나 장애물을 마주친다면, 현재 이동 좌표의 직전 좌표를 사용하고 현..

📖 문제 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 💡 풀이 방식 • 구현, 시뮬레이션, BFS 필요 자료구조 - 4방 탐색용 dx/dy 배열 - 땅에 붙어있는 클러스터 위치 저장용 큐 (bfs 수행) - 땅에 붙어있는 클러스터 표시할 방문 표시 배열 - 공중에 떠있는 미네랄 위치 저장용 리스트 1. 왼쪽, 오른쪽 번갈아가며 주어진 높이의 미네랄을 파괴한다. private static void solve(int row, int i) { if(i % 2 == 0) { // 왼 > 오 for(int j = 0 ; j < ..