# breadth first search
[백준] 연구소
삼성 기출 문제중 하나이다. 3개의 벽을 꼭 설치해야 하고 모든 바이러스가 상하좌우로 퍼진다는 가정하에 가장 많은 안전지대를 만들면 된다. 결국 이 문제의 핵심은 어느 위치에 벽을 두냐에 로직이였고 아이디어만 떠올리면은 쉽게 풀 수 있는 문제다. 솔직히 이 문제를
[백준] 치즈
분명히 쉬운 문제인데 생각보다 좀 고전했다. 복잡하게 생각하는 내 버릇 때문에 잘 풀지 못하고 고민했던거 같다. 치즈가 녹는 문제의 성질을 이해 했다는 가정하에 이 문제의 핵심은 "가장 자리"에 있는 치즈들만 녹일 수 있게 코드를 만들어야 했다. 안쪽에 있는 치즈는 녹
[백준] 죽음의 비
꽤 빈번히 나오는 완전탐색류 라고 생각했지만 생각보다 조건이 까다로운 부분도 있어서 애를 좀 먹었다. 가장 밑에 안전지대 까지 가는 최소 경로를 구해야 하는 문제였지만 U 로표시되어있는 우산의 내구도를 신경 써주면서 가야했었다. 이 문제는 예전에 SK 코테에서 풀었던
백준 16234, 인구 이동
업로드중..https://www.acmicpc.net/problem/16234구현, 시뮬레이션BFS: 국경선 오픈 및 같은 연합인 칸들 찾기인구 이동이 없을 때까지 반복breakFlag == true인 경우, 반복 종료2중 for문으로 각 나라 칸들 차례로 확
백준 23288, 주사위 굴리기 2
https://www.acmicpc.net/problem/23288구현, 시뮬레이션: 주사위 1칸 이동, 주사위 이동 방향 결정BFS: 주사위 1칸 이동 후 획득 점수 계산1) 주사위 1칸 이동이동 방향에 칸이 있는 경우, 해당 이동 방향으로 1칸 굴러감이동
백준 17142, 연구소 3
https://www.acmicpc.net/problem/17142조합(백트래킹 + 브루트포스): 전체 k개 바이러스에서 활성화 시킬 m개 선택BFS: 바이러스 퍼뜨리기1) 활성화 시킬 바이러스 m개 선택void backtrack(int virusIdx, in
백준 16236, 아기 상어
https://www.acmicpc.net/problem/16236구현, 시뮬레이션BFS먹을 수 있는 물고기 위치 탐색PriorityQueue / 정렬BFS 탐색하면서, 먹을 수 있는 물고기 찾으면 PQ에 저장1) 먹을 수 있는 물고기 탐색현재 아기 상어 위치
백준 20058, 마법사 상어와 파이어스톰
https://www.acmicpc.net/problem/20058 1. 아이디어 > 구현, 시뮬레이션, BFS 1) map을 2^L x 2^L 부분 격자로 나눈 후, 부분 격자 단위로 시계 방향 90도 회전 2중 for문으로 map 확인 => i, j
백준 14502, 연구소
https://www.acmicpc.net/problem/14502조합(백트래킹 + 브루트포스), BFS벽을 반드시 3개 세워서, 바이러스가 최소로 퍼지도록 함 1) 전체 빈 칸에서 벽을 세울 빈 칸 3개 선택세울 벽 위치를 3개 선택 완료한 경우 2), 3)
[BOJ][BFS] 11403. 경로찾기
Source: https://www.acmicpc.net/problem/11403 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.첫째 줄에 정점의 개수 N (1
백준 21609, 상어 중학교
https://www.acmicpc.net/problem/21609BFS, 구현, 시뮬레이션블록 그룹의 기준 블록 = 일반 블록 중, 행 번호가 가장 작은 블록 -> 열 번호가 가장 작은 블록오토 플레이: 블록 그룹이 존재하는 동안 반복1) 크기가 가장 큰 블
[백준] 레이저 통신
전 포스팅에서 경주로 건설을 먼저 풀었던 이유는 사실 이 문제를 푸는데 좀 더 개념이 잡히고 도전 해보고 싶었다. 시뮬레이션 골드 3이상 문제들은 솔직히 좀 생각도 많이 해야하고 난이도가 있는 느낌이다. C 라는곳에서 레이저를 발사하고 다른 C에 그 레이저가 전달 되야
경주로 건설
카카오코테 대비 문제를 계속 풀어보았다. 이 문제는 내가 군대 있었을때부터 계속 풀어봤고 풀이 또한 여러번 읽으면서 완전히 익숙한 문제다. 그런데 내 예전 풀이가 테스트케이스가 추가된 순간부터 통과가 안됐었고 군대에 있을때만 해도 도저히 다시 풀어볼 용기가 안났었고 고
백준 19238, 스타트 택시
https://www.acmicpc.net/problem/19238최단경로 => BFS현재 택시 위치 -> 우선순위 높은 승객 위치=> BFS 1택시에 태운 승객 위치 -> 태운 승객의 목적지=> BFS 2map\[]\[]에 승객 출발 위치 표시 (승객 번호)
백준 13460, 구슬 탈출 2
https://www.acmicpc.net/problem/13460시뮬레이션 + BFS최단 거리(최소 동작 횟수) => BFS !!탐색 노드 상태: (빨간 구슬 위치), (파란 구슬 위치), 현재까지 기울이기 동작 횟수※ 문제 핵심 ①) BFS 탐색 노드 상태
백준 1325, 효율적인 해킹 - DFS / BFS
https://www.acmicpc.net/problem/1325"A가 B를 신뢰" 하는 경우, B를 해킹하면 A도 해킹 가능=> 신뢰 관계 (방향이 있는 간선)을 따라 그래프 탐색=> 인접 리스트 List<Integer>\[] lists에 간선 정보 저
[백준] 로봇
그래도 오랜만에 재미있는 BFS 문제를 풀어보았다. 솔직히 처음 읽자마자 아 이문제는 3차원 방문 벡터를 사용해야 되겠고 방향만 잘 읽으면은 문제 없이 풀 수 있겠다 싶었는데 너무 뜬금포인 부분에서 생각보다 시간을 너무 많이 소모해서 허탈하게 푼 문제다. 로봇이라는 객
[백준] 불!
조금 변형된 유형의 문제를 찾아서 풀어봤다. 솔직히 이제 백준 그래프 추천 문제는 정말로 많이 풀게 된거같다. 이번 문제도 큰 문제없이 한번에 통과 됐고 설명에 대한 해석만 본 후에 잘 풀었다. 일반적으로 시뮬레이션이 섞인 BFS 탐색 문제에서 두 물체가 움직이게 되면
[백준] 빙산
백준 그래프 추천문제인 빙산 문제를 풀어봤다. 문제 자체는 꽤 쉬운데 쉽게 실수를 할 수 있을법한 문제다. 그래도 솔직히 이런 시뮬레이션이 섞인 BFS 문제를 백준에서 많이 풀어봐서 그런지 문제를 읽자마자 어떻게 풀어야할지 감이 왔고. 코드를 다 만든 후 에도 다시 읽
[백준] 직사각형 탈출
처음 문제를 읽고 정말 단순한 BFS 구현인줄 알고 바로 풀려고 했는데 생각보다 까다로운 구현이었다. 직사각형의 모양 H 와 W 로 주어졌고 난 처음에 직사각형 형태를 벡터로 담은 후에 상하좌우로 탐색을 해줘야 할까 고민했었다. 틀린 답그러나 이 접근이 틀렸단걸 알았다