BFS19 [백준 9205] 맥주 마시면서 걸어가기 www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 어떻게 접근해야 하는지 어려웠던 문제이다. 관건은 편의점마다 노드 번호를 붙여서 연결 그래프를 만드는 것이 핵심이었다. 모든 편의점 위치를 저장한다음 각 편의점마다 접근가능한 (맨해튼거리 1000이하) 편의점을 연결리스트에 저장한다. 연결리스트를 만들었다면 bfs를 사용해서 목적지인 n+1을 방문했는지 확인한다. 참고로 dfs를 써도 방문확인이 가능하다. #include #include #include #.. 2021. 1. 31. [백준 16918] 봄버맨 www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 뭔가 쉬운데 헷갈렸던 문제.. bfs가 살짝 필요한 구현문제이다. 3초짜리폭탄을 설치하고 1초를 냅둔다. 2초에 빈자리에 폭탄을 설치한다. 폭탄이 0초가 되면 터지고 주변에 폭탄이 있다면 같이 터진다. 그뒤로 폭탄 설치와 폭발이 반복이다 폭탄 설치는 짝수 초에 계속된다. 그래서 남은 폭탄 시간을 저장하는 이차원 배열 time을 만들었다. 폭탄 설치 시 3이 저장되며 폭탄이 없는 공간은 -1이다. 배열이 0이 되면 폭탄이 터져서 .. 2020. 12. 27. [백준 16236] 아기 상어 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net bfs를 사용하는 구현문제. 조건이 너무 많다. 1. 물고기가 있는 지 확인 2. 있다면 먹기 3. 여러 마리라면 우선순위가 있다. 가까운 물고기 -> 위쪽 -> 왼쪽 에 있는 물고기 먹기 4. 없으면 엄마 상어 부르기 이다. 물고기를 먹기 위한 조건은 크기보다 작은 경우에만 가능하다. 크기가 동일하면 지나가는 것만 가능 크기가 커지는 조건은 물고기를 크기만큼 먹었을 때 크기가 1만큼 커진다. 1 2 3.. 2020. 12. 26. [백준 17142] 연구소 3 www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 2와 비슷한 문제이다. 차이가 있다면 비활성 바이러스가 활성 바이러스를 만나면 활성바이러스가 된다는 점이다. 비활성-> 활성바이러스가 되는 시점에선 시간+1을 해주지 않아도 된다. 활성바이러스로 부터 다시 바이러스가 퍼지기 시작하기 때문. 그림으로 따지자면 다음과 같다. 위그림은 전부 빈곳 일때이다. 빈곳일때는 그냥 +1 해주면 된다. 하지만 비활성 바이러스가 활성 바이러스가 되면 시간에 영향을 주지 않는다. 이.. 2020. 12. 22. 이전 1 2 3 4 5 다음
