DFS

[JAVA] 백준 4991 : 로봇 청소기

문제 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 해결 방법 처음엔 우선순위큐를 활용한 BFS로 거리를 계산해서 최소 거리를 알아내면 될 것 같아서 시도해보았는데, 최소 거리로 움직이면서 다음으로 탐색하는게 전체적으로 더러운 칸을 모두 제거하였을 때 최소 거리가 아닐 수도 있다고 한다. 그래서 처음에 짠 코드는 실패하였다. 해결한 방법은 다음과 같다. 먼저 로봇과 각 더러운 칸들 간의 거리를 정리할 배열을 생성해두고 값을 넣어주어야한다. BFS 탐색을 활용해서 로봇에서 더러운 칸의 거리들, 더러운 칸들과 더러운 칸..

[JAVA] 백준 2638 : 치즈

문제 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 해결 방법 하루가 지나면 녹는 치즈들이 며칠 후에 완전히 녹는지 알아내는 문제다. 외부 공기와 접촉한 부분이 2부분 이상이면 녹게 되는데, 치즈로 둘러쌓여 있는 부분이면 외부 공기에 해당하지 않는다. 문제에서 가장자리들에는 치즈가 놓이지 않는다고 하였기 때문에 초기에 0, 0 에서 탐색을 시작해서 탐색이 가능한 부분이 외부 공기에 해당하는 부분이라고 생각하면 된다. 외부 공기에 해당하는 부분은 3으로 초기화를 해준다음에 치즈의 상하좌우에 3인 부분..

[JAVA] 백준 3109 : 빵집

문제 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 해결 방법 처음엔 BFS 로 탐색을 시도했었는데 문제가 파이프를 생성하고 그 파이프가 지나간 길을 제외한 다른 길에 새로운 파이프를 연결하는 방식이라 DFS로 시작점부터 끝점까지 한 번에 파악하는게 DFS가 맞는 것 같아서 수정해서 풀었다. 처음 생각했던 것은 파이프가 이어지는 방식이다. 문제에서 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로만 이동이 가능하다고 했는데, 왼쪽 제일 윗 칸인 (0, 0)에서 부터 탐색을 시작하는 점을 감안하여 보면 오른쪽 위, 오른쪽,..

[JAVA] 백준 14267 : 회사 문화 1

문제 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 해결 방법 생각보다 까다로웠던 문제였다. 이 문제에서 주의 깊게 봐야 하는 것은 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이라는 것. 처음엔 인접리스트를 구현한 후에 칭찬을 받은 번호부터 칭찬의 수치를 dfs로 탐색하며 업데이트하는 방법을 사용했다. 다음 탐색할 곳을 찾는 것은 단순히 현재 탐색하는 곳보다 숫자가 크면 탐색하는 조건문을 사용했다. 하지만 최초 칭찬의 횟수만큼 계속 탐색을 진행하게 되어 시간 초과가 발생해서 다른 방법..

[JAVA] 백준 15900 : 나무 탈출

문제 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 해결 방법 천천히 문제를 읽어보고 주어진 입력을 손으로 그려보았다. 그 결과 알 수 있는 점은 모든 리프 노드에서 루트 노드까지 거리가 홀수일 경우 성원이가 이길 수 있고, 짝수일 경우 성원이가 질 수밖에 없음을 알 수 있다. 예제 입력 2를 그림판으로 그려본 것인데, 게임 말은 리프노 노드에 위치한다고 했기 때문에 3 과 4에서 시작한다. 각각 2와 1을 거쳐 2칸, 2칸, 즉 총 4칸을 움직여야 모든 게임 말이 제거된다. 그렇기 때문에 모든 리프 노드에서..