17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지 확산 과정을 이해하지 못한 점과 DFS + 시뮬레이션이라 생각한 것 때문에 푸는데 오래 걸렸다. 어찌어찌 DFS + 시뮬레이션을 통해 아주 느린 속도로 통과를 한 후, 다른 블로그를 찾아보니 단순 구현 + 시뮬레이션이었고, 문제 분류도 그랬다. 미세먼지 확산은 모두 "동시"에 일어난다. 이를 구현하기 위해 각 칸이 받는 영향(먼지를 퍼트려 먼지가 줄어들거나, 옆 칸의 먼지가 확산되어 먼지가 늘어나거나)을 기록할 배열이 따로 있어야 한다. 각 칸의 증감량..
전체 글
17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 대각선으로 이동할 때 3칸을 고려해야한다는 걸 뒤늦게 알아 해결한 문제 BFS로 풀었는데, 대부분 DFS로 풀었고 DP로 푼 경우도 있는 것 같다. 풀고서 다시 생각해보니 DP도 좋은 풀이인 것 같다. BFS로 풀 경우 조건을 많이 걸어 경우의 수를 좀 많이 제외시켜줘야 할 것 같다. 파이프의 앞 쪽 좌표와 놓인 방향을 큐에 넣어 BFS를 수행했다. 집의 벽(문제에서 1로 표현한 벽 말고)에 닿도록 가로, 세로로 놓이게 된다면 그 곳이 (..
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨집을 선택하기 위한 백트래킹이 주요한 문제였다. 입력을 받을 때, pair 배열 house와 chicken에 가정집과 치킨집 각각의 좌표를 저장하며 개수를 카운트 했다. 이후 각 집에서 모든 치킨 집까지의 거리를 2차원 배열 dist에 저장 (row는 가정집 좌표 배열 house의 인덱스, column은 치킨집 좌표 배열 chicken의 인덱스) 백트래킹으로 치킨집 m개를 선택 후, 각 집에서부터 선택된 치킨집들을 대상으로 치킨 거리 계산..