BFS

[백준 17142] 연구소3 (Java, BFS) 문제 출처 : 링크 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 모두 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 올해 상반기 삼성전자 역량테스트 문제다. 예전에 나온 삼성 기출 '연구소'에서 조건만 좀 더 추가된 문제 3가지 조건만 잘 기억하고..

[백준 2206] 벽 부수고 이동하기 (Java, BFS) 문제 출처 : 링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 지난번에 포스팅한 미로만들기와 유사한 방법으로 접근해야하는 문제다. 이 문제의 정답률은 훨씬 낮은데, N과 M의 ..

[백준 16236] 아기 상어 (Java, BFS) 문제 출처 : 링크 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크 www.acmicpc.net 삼성 코딩테스트 기출 문제인 아기 상어 문제를 읽고 이해할 때 여러 제한 조건을 잘 고려해서 구현해야 한다. 하나라도 놓치면 디..

[백준 2665] 미로만들기 (Java, BFS) 문제 출처 : 링크 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 시작부터 끝이 정해져 있고, 시작 방부터 끝 방까지 방의 색을 최소로 바꿔서 이동시켜야 하는 문제다. BFS라는거는 바로 알 수 있지만, 단순하게 생각하면 까다로울 수 있는 문제다. 평소처럼 boolean으로 visit 배열을 만들어 체크하는 것이 아닌, int형으로 각 위치마다 방을 바꾼 횟수를 저장시키며 나아가는 방법을 익힌 문제..! 시작할 때 visit 배열을 모두 무한대 값으로 초기화 해두고..

[백준 16234] 인구 이동 (Java) 출처 : 링크 2018년 하반기 삼성 코테 기출이다. DFS와 BFS 모두 사용이 가능하고, 인구 이동이 가능할 때까지 계속 진행해서 횟수를 출력해주면 된다. 이동이 가능한 배열마다 같은 숫자를 저장하도록 2차원 배열을 하나 더 만들었다. (copymap) DFS를 통해 조건에 맞는 이동가능 배열끼리 묶어주고, 해당 map의 값을 모두 더해 평균을 내서 저장시켰다. 평균을 구하는 반복문을 따로 만들어서 사용하면 시간초과로 풀 수 없으므로 먼저 리스트를 생성해 DFS를 호출하는 반복문 안에서 평균 값 계산을 같이 해야 시간을 줄일 수 있었다. 12345678910111213141516171819202122232425262728293031323334353637383..

[백준 1012] 유기농 배추 (DFS, BFS) 문제 출처 : 링크 DFS와 BFS를 활용해서 모두 풀 수 있는 문제다. 1로 표시된 구간마다 묶어서 총 몇 개가 있는지 구해야 한다. 예전에 처음 공부하면서 풀었던 백준 2667번 단지번호 문제(링크)와 유사하다. DFS 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenize..