본문 바로가기

전체 글108

백준 14502번 : 연구소 문제 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 구현 방법 벽 3개를 세울 수 있는 모든 경우의 수를 구해야합니다. 미리 빈칸의 개수와 좌표를 저장해두어 빈칸 중 3개를 구하여 구할 때마다 dfs를 돌려 바이러스를 퍼트려줍니다. 바이러스가 적게 퍼져야 안전영역이 커지므로 바이러스가 퍼지는 개수를 구해주어 이들의 최솟값을 구하여 안전영역의 최댓값을 구해줍니다. 구현 코드 package BOJ.Gold; import java.io.BufferedReader; impor.. 2021. 4. 5.
백준 1600번 : 말이 되고픈 원숭이 문제 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 구현 방법 최소한의 동작을 구해야 하기 때문에 bfs를 사용하여 풀어주었습니다. 보통의 bfs/dfs 문제와 다르게 k번만 따로 동작을 할 수 있습니다. 평소에 방문처리를 R, C 로만 했다면 이 문제는 말 움직임을 관리하는 K까지 처리를 해줘야하므로 3차원 배열을 사용해주어야 합니다. bfs를 돌려 원숭이의 움직임으로 움직이고 만약 현재 원숭이가 말의 움직임을 할 수 있다면 말의 움직임도.. 2021. 4. 5.
백준 9205번 : 맥주 마시면서 걸어가기 문제 www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 구현 방법 플로이드-와샬 알고리즘으로 풀 수도 있지만 너무 어려워,,서 bfs로 풀어주었습니다. 처음 시작은 상근이의 집이므로 큐에는 상근이의 집 좌표를 저장, 이동하는 곳으로는 편의점과 락 페스티벌로 입력받은 좌표를 List에 저장하였습니다. 다음 bfs를 돌려 현재 좌표에서 다음 갈 곳의 좌표간의 거리를 구해준 다음 방문을 하지 않았고 맥주가 남아있을 경우에만 큐에 추가해주었습니다. 맥주가 다 떨.. 2021. 4. 5.
백준 19236번 : 청소년 상어 문제 www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 구현 방법 갈 수 있는 곳 까지 갔다가 다시 돌아와야 하기 때문에 dfs를 사용하여 풀어주었습니다. 순서는 물고기 먹기 -> 물고기 이동 -> 상어 이동 입니다. 좌표, 방향, 생존여부를 저장할 fish클래스를 생성하여 물고기 배열을 만들어 주었습니다. 4X4 고정 즉 물고기는 항상 16개이므로 크기는 17개로 만들어주었습니다. 상어가 (0,0) 좌표에 있는 물고기를 먹으면서 시작됩니다... 2021. 4. 5.

티스토리툴바