https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net BFS를 응용한 단순 구현문제이다. 내가 푼 알고리즘은 다음과 같다. 1. 외곽을 모두 돌면서 빈공간의 위치를 덱에 넣고, 열쇠는 먹은 후 빈공간으로 바꾼다음 위치를 덱에 넣고, 문은 맵에 문 위치를 저장한다. (이때 같은 문이 여러개 있을 수 있으니, 맵에 리스트를 저장한다.) (열쇠는 같은 열쇠가 여러개 있을 수 있으니 집합에 저장한다.) 2. 현재 갖고 있는 열쇠로 열 수 있는 문을 모두 연다. 문을 열..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 개인적으로 solved.ac 난이도에 비해 힘들게 푼 DP 문제이다. 이 문제는 1가지만 떠올리면 정말 정말 쉽게 풀린다. 현재 문제에서 요구하는게 '없애야 하는 전깃줄 개수의 최솟값'이다. 하지만 전체 전깃줄의 개수가 고정되어 있다는 점에서 이를 뒤집어 생각하면 '남겨야 하는 전깃줄 개수의 최댓값'을 구해서 이 문제를 풀 수도 있다. 이렇게 발상의 전환만 성공했다면, 이 문제는 단순한 LIS 문제로 바..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이 문제는 그래프 탐색 문제를 조금 꼬아낸 문제이다. 제일 나이브한 풀이는 각 벽에 대해 BFS를 수행하는 것인데, 아무리 봐도 이건 시간 초과 풀이이다. 전체 영역이 최대 100만 칸짜리 2차원 배열인데, 이를 중복해서 순회하면 시간 초과가 안날 수 없다. 2차원배열을 한번만 순회하여, 그 결과를 이용해 답을 도출해야 한다. 그래서 나는 비어있는 영역에 대해 BFS를 수행하..
