BFS

📖 문제   18428번: 감시 피하기NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복www.acmicpc.net   💡  풀이 방식• 조합(DFS) + BFS 1. 격자를 입력받으면서 학생 S의 위치, 선생님 T의 위치, 빈 칸 X의 위치를 각 리스트에 저장해둔다.이러면 나중에 완전탐색으로 학생, 선생님, 장애물 위치를 따로 안 찾아도 된다.for(int i = 0 ; i   2. 빈 칸 X의 위치들 중 3개를 뽑고, 해당 위치에 장애물을 심었을 때 모든 학생들이 감시를 피할 수 있는지 BFS로 탐색한다.private static void dfs(int..

📖 문제   10026번: 적록색약적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)www.acmicpc.net   💡  풀이 방식• BFS 일반인과 적록색약의 경우를 나눠서 BFS를 수행한다.1) 일반인의 경우, RGB를 3색을 각각 다르게 본다. R구역과 G구역과 B구역으로 나뉜 구역 수를 구하는 BFS를 수행한다.visited1 = new boolean[N][N];for(int i = 0 ; i private static void bfs1(int x, int y, char c) { Queue q = new ArrayDeque(); q.ad..

📖 문제  17141번: 연구소 2인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러www.acmicpc.net   💡  풀이 방식• 조합(DFS) + BFS필요 자료구조- 인접한 4방향 칸 탐색용 dx/dy 배열- BFS용 방문 표시용 2차원 boolean형 배열- 바이러스 위치 저장용 리스트 virusList- 뽑은 바이러스 M개 저장할 임시 리스트 tmpList  1. 연구소 정보를 저장하면서, 바이러스 위치도 저장한다.2. 조합(DFS)으로 바이러스 위치들 중 M개를 뽑아 뽑은 칸에서 BFS 탐색을 통해 바이러스를 퍼뜨리는 시간을 계산한다. [바이러스 위치들 중 ..

📖 문제 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 💡 풀이 방식 • BFS + 시뮬레이션 1. 배열을 시계 방향으로 90도 회전시킨다. (그림 참고) private static void rotate(int r, int c, int v, int[][] tmp) {// tmp : 회전 후 값 저장용 배열 for(int i = 0 ; i < v; i++) { for(int j = 0 ; j < v ; j++) { tmp[r + i][c + j] = A[r + v - 1 - j][c + i]..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • BFS 1. 범위를 2배로 늘려 0~100 으로 격자 크기를 늘린 2차원 int형 배열을 생성한다. int[][] board = new int[101][101]; → Why? 선이 아닌 좌표를 기준으로 하므로 크기를 2배로 확장해야 제대로 탐색을 할 수 있기 때문이다. (참고) 2. rectangle 배열을 돌며, 내부와 테두리를 구분해 위에서 만든 배열에 값을 저장해준다. (여기서도 2배해준 값 사용하기) for(int[] r : rectangle) { fill(2*r[0], 2*..

📖 문제 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 💡 풀이 방식 • 다익스트라 (우선순위 큐) 최단 경로인 지점을 항상 우선으로 탐색하고자 점프 횟수 기준 오름차순 정렬하는 우선순위 큐를 활용한다. class Node implements Comparable { int x, y, w; public Node(int x, int y, int w) { this.x = x; this.y = y; this.w = w; } @Override public int compareTo(Node n) { // 💥 ..

📖 문제 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 💡 풀이 방식 • BFS . 모래성이 없는 노드를 중심으로 생각한다! 모래성이 없는 노드의 주변 8방향 노드 中 모래성이 있는 노드의 튼튼함을 하나 깎는다. 그러다 보면 결국 가운데 모래성이 없어지게 되는데, 이 때는 그 위치를 노드에 추가해주면 된다. 💥 유의사항 이미 한 번 확인한 모래성이 없는 노드는 다시 확인할 필요가 없기 때문에 새롭게 모래성이 없어진 노드만 탐색한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 1..

📖 문제 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 💡 풀이 방식 • BFS 필요 자료구조 - 로봇 객체 (행, 열, 방향, 명령 횟수) - 3차원 boolean형 방문 표시 배열 : [행][열][방향] ⭐ - dx/dy 배열 동서남북 배열 1. 격자를 입력받는다. 2. 시작점 위치,방향과 도착점 위치,방향을 입력받는다. String[] s1 = br.readLine().split(" "); start = new Robot(Integer.parseInt(s1[0]) -1, Integer.parseInt(s1[1])..

📖 문제 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 💡 풀이 방식 • BFS 외벽과 닿는 모든 면을 정육각형으로 돌리기 위해 격자 판 숫자를 저장할 map 배열과, 벽 개수를 저장할 2차원 배열 result의 크기는 [행+2][열+2]로 설정한다. map = new int[H+2][W+2]; // 외벽과 닿는 모든 면을 정육각형으로 돌리기 위해 +2 result = new int[H+2][W+2]; // 벽 개수 저장 리스트 visited = new boolean[H+2][..