본문 바로가기

백준98

백준 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.
백준 15683번 : 감시 문제 www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 구현 방법 cctv가 가질 수 있는 경우의 수를 다 계산하여 사각지대의 최소 크기를 구해줘야 합니다. cctv의 좌표, 번호를 리스트에 저장하고 리스트의 크기만큼 방향을 가지는 순열을 구해줍니다. 선택된 방향으로 가능성을 다 확인 후 사각지대 개수를 카운트 하여 제일 최솟값을 출력해줍니다. cctv5는 어느 방향 상관없이 인접한 곳을 다 확인하므로 반복을 피하기 위해 따로 저장해주어 감시를 해주.. 2021. 3. 24.
백준 2638번 : 치즈 문제 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 구현 방법 단계적으로 생각해보았습니다. 1. 치즈 겉 공기 구하기 - (0, 0)은 무조건 빈 칸, (0, 0)부터 인접한 곳이 빈 칸일 때 bfs 돌려 check 배열에 1로 저장. 치즈 속 공기는 1로 둘러쌓여 있기 때문에 치즈 속 공기까지 도달하지 못함. 2. 치즈 속 공기 구하기 - check 배열 값이 0이고 cheese 배열 값이 0이면 치즈 속 공기 -> 2로 변경 3. 사라질 치즈 .. 2021. 3. 24.

티스토리툴바