본문 바로가기

BFS

 (7)
[프로그래머스] 경주로 건설 / 2020 카카오 인턴십 - JAVA 🔗 문제 링크 [프로그래머스] 경주로 건설 / 2020 카카오 인턴십 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 📝 풀이 과정 시작점인 [0, 0]부터 [N - 1, N - 1]까지 경주로를 건설해 최솟값을 구하는 문제다. 단, 경..
[백준] 2638번: 치즈 - JAVA 🔗 문제 링크 BOJ 2638번:치즈 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 📝 풀이 과정 문제에서 외부 공기라는 개념이 존재하기 때문에, 가장자리는 항상 공기이므로 먼저 [0, 0]에서부터 BFS를 통해 0인 칸은 모두 10으로 변경해주었다. 이후 반복문을 돌며 치즈 칸에서 상하좌우 칸의 합이 20이상일 경우 외부 공기가 2칸 이상 존재한다는 것을 의미하므로 외부 공기로 변화시키는 BFS를 위한 Queue에 삽입한다. 반복문을 돌며 Queue 내부에 있는 값들을 10으로 변경하고 접촉한 공..
[백준] 15591번: MooTube (Silver) - JAVA 🔗 문제 링크 BOJ 15591번: MooTube (Silver) 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 📝 풀이 과정 문제를 보면 N까지의 영상이 존재하는데 영상끼리 가는 경로는 무조건 존재하며, 개수는 N - 1개라고 주어진다. 이것으로 주어진 그래프가 Spanning Tree(신장 트리, 최소 연결 부분 그래프)임을 알 수 있다. 따라서, 만약 A → B로가는 연결이 끊어진다면 A → B로는 갈 수 없게 되며 A에서 출발해 B에서 연결된 다른 간..
[백준] 16236번: 아기 상어 - JAVA 🔗 문제 링크 BOJ 16236번: 아기 상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 📝 풀이 과정 문제의 규칙을 먼저 정리해보았다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다. 자신의 물고기보다 작은 물고기만 먹을 수 있다. 더 이상 먹을 물고기가 존재하지 않는다면 도움을 요청한다 먹을 수 있는 물고기가 많다면 거리가 가깝거나, 가장 위에 있거나, 가장 왼쪽에 있는 물고기 순으로 먹는다. 물고기가 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1씩 증가한다. 문..
[백준] 9019번: DSLR - JAVA 🔗 문제 링크 BOJ 9019번: DSLR 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 📝 풀이 과정 숫자와 문자열을 동시에 저장해야 하기 때문에 Register class를 만들어주었다. class에서 D, S, L, R을 한 연산을 처리한 결과를 반환해주기로 하였다. D 연산의 경우 n을 2배한 뒤 값이 9999보다 크다면 %10000 값을 반환하라고 하지만 9999보다 작은 경우에는 %10000을 한다면 원래 값이 반환되므로 num * 2 % 10000을 반환한다. S 연산의 경우 n =..
[백준] 7576번: 토마토 - JAVA 🔗 문제 링크 BOJ 7576번: 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📝 풀이 과정 익은 토마토가 주변의 앞, 뒤, 왼쪽, 오른쪽 4방향의 안익은 토마토를 익게 만드는 총 일수를 구하는 문제이다. 전형적인 BFS 문제의 구조를 띄고 있다. 처음 입력을 받으며 익은 토마토는 Queue에 넣는다.나의 경우 Queue에 int[] 배열로 토마토의 위치를 저장하였다. 마지막에 안익은 토마토가 존재할 경우 -1을 출력하는 조건 존재하기 때문에 이를 처리하기 위해 안익은 토마토가 등장..
[백준] 2667번: 단지번호 붙이기 - JAVA 문제 링크 BOJ 2667번: 단지번호 붙이기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. www.acmicpc.net 풀이 과정 모든 지도를 돌며 연결되어 있는 1을 카운트하며 갯수를 세면 되기 때문에 BFS사용하기로 했다. 개인적으로 map을 처리할 때, int형보다 boolean이 처리하기 쉬워서 입력값을 1일 때 true, 0일 때 false로 바꾸어 저장하였다. 이중 반복문을 통해 map배열에 true가 있는지 탐색하고 만약 존재한다면 해당 칸부터 시작해 상하좌우를 탐색하며 queue에 넣으며 방문한 칸을 false로 변경하여 ..

티스토리툴바