BOJ 16236번 아기 상어 문제 자바(java) 풀이 랭크 : 골드5 백준 16236번 아기 상어 문제 정리 NxN 크기의 공간 M마리의 물고기 아기 상어 1마리 한 칸에는 물고기가 최대 1마리 존재(없거나 1마리) 초기 아기상어의 크기는 2 1초에 상하좌우 한 칸씩 이동 자신의 크기보다 큰 물고기가 있는 칸 제외 모든 칸 지나갈 수 있음 자기보다 작은 물고기 먹을 수 있음, 크기 같으면 지나만 갈 수 있음 이동 결정 알고리즘 더 이상 먹을 수 있는 물고기가 없으면 엄마에게 도움을 청함 먹을 수 있는 물고기가 1마리면 그 물고기를 먹으러 감 먹을 수 있는 물고기가 1마리 보다 많다면, 거리가 가장 가까운 물고기를 먹으러 감 거리: 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 ..

BOJ 11724번 연결 요소의 개수 c++ 및 java 풀이 난이도: 실버3 백준 11724번 연결 요소의 개수 문제 정리 방향 없는 그래프가 주어질때 그래프의 연결 요소(Connected Component)의 개수를 구하시오 연결 요소 란?? 그래프는 여러 개의 고립된 그래프로 구성될 수 있는데 서로 연결된 여러 개의 고립된 그래프 각각을 연결 요소라고 한다. 연결 요소의 특징 연결 성분에 속한 모든 정점을 연결하는 경로가 있어야 한다. 또 다른 연결 성분에 속한 정점과 연결하는 경로가 있으면 안된다. BFS, DFS를 통해 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결성분이 된다. 문제 접근 처음에 주어진 예제를 잘못 보고 문제를 이해를 잘 못해서 빨리 풀지 못했습니다 ㅠㅠㅠ 예제를 똑바..

BOJ 달이 차오른다, 가자 문제 자바(java) 풀이 난이도: 골드1 백준 1194번 달이 차오른다, 가자 문제 정리 미로를 탈출하려 한다. 미로는 다음과 같이 구성되어 있다. 빈 곳: 언제나 이동 가능(.) 벽: 절대 이동 불가(#) 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 잡는다(a - f) 문: 대응하는 열쇠가 있을 때만 이동 가능(A - F) 민식이 위치: 빈 곳, 현재 서 있는 곳 (숫자 0) 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳. 탈출로(숫자 1) 민식이는 수평, 수직으로 이동가능하다. 탈출하는데 걸리는 이동 횟수의 최솟값을 구하시오 열쇠와 문은 여러 개일 수도 있다. 문에 대응하는 열쇠가 없을수도 있다. 0은 1개, 1은 적어도 한 개 있다. 열쇠는 여러..

BOJ 7569번 토마토 문제 자바(java) 풀이 난이도: 실버1 백준 7569번번 토마토 문제 정리 창고에 보관한 토마토중에 잘 익은 것과 익지 않은 것이 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익게 된다. 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 이다. (대각선 X) 창고의 토마토들이 며칠이 지나면 다 익게 되는지 최소 일수를 구하려 한다. 모든 칸에 토마토가 들어있지 않을 수 있다. 1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토가 들어있지 않음 저장될 때 부터 모든 토마토가 익어있는 상태이면 0을 출력 토마토가 모두 익지 못한다면 -1 출력 문제 접근 3차원 형태의 배열을 가지고 bfs 탐색을 통해 토마토를 익혀가면 된다. 3차..

BOJ 1012번 유기농 배추 문제 자바(java) 풀이 난이도: 실버2 풀이시간: 20분 백준 1012번 유기농 배추 설치 문제 정리 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 배추가 상하좌우로 붙어있으면 인접해있다고 본다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 서로 퍼지므로 총 몇 마리의 지렁이가 필요한지 알 수 있다. 다음과 같이 입력이 주어진다 TC 개수 가로 세로 배추개수 맵 각 TC에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다. 문제 접근 이 문제는 bfs를 이용하여 영역의 개수를 구하는 것과 같은 문제입니다. bfs를 통해 1로 이어져 있는 영역은(배추가 이..

프로그래머스 단어 변환 자바(java) 풀이 Level 3 BFS/DFS 단어 변환 문제 정리 두 개의 단어 begin, target과 단어의 집합이 있다. 다음 규칙을 이용하여 begin에서 target으로 단어를 변환하는 가장 짧은 변환을 찾으려 한다. 규칙1: 한 번에 한 개의 알파벳만 바꿀 수 있다. 규칙2: words에 있는 단어로만 변환할 수 있다. 최소 몇 단계의 과정을 거쳐 target으로 바꿀 수 있는지 찾아라. 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다. words에는 3개 이상 50개 이하의 단어가 있습니다. 변환할 수 없는 경우에는 0을 return 합니다. 문제 풀이 이 문제는 bfs의 개념을 이용하면 생각보다 간단히 풀 수 있습니다. 하지만 그것까지 떠..