dfs

[백준] 9205 맥주 마시면서 걸어가기 (JAVA)

✉️문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 📝 접근 DFS와 BFS의 경계가 모호한 문제인 것 같다. 개인적으로 Queue를 이용하는 것 보다는 DFS가 좋아 DFS를 이용하여 풀이하였다. 🗝 문제풀이 1. 첫 입력으로 테스트 개수가 주어진다. 따라서 테스트 개수를 이용한 for문을 돈다. 2. 편의점의 수가 주어지는데, 이 좌표들을 store 배열에 저장하였다. 3. 편의점을 방문했는지 체크하기 위해 visited 배열을 ..

[백준] 2573 빙산 (JAVA)

✉️문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 📝 접근 이 문제를 위해서 필요한 기능은 크게 2가지이며, BFS와 DFS를 모두 이용한다. 1. 빙산의 개수를 확인하는 코드 (DFS) 2. 빙하를 녹이는 메소드 (BFS) TIP ! 배열을 선언할 때 x,y 변수명을 이용하면 더 헷갈리는 것 같다. 이 때는 row와 col 변수명을 이용하는 것이 더 편하다. 🗝 문제풀이 1. 빙산의 개수를 확인하는 코드 (두개의 메소드로 분리하였..

[백준] 2468 안전 영역 (JAVA)

✉️문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 📝 접근 DFS, BFS를 이용하여 문제 풀이가 가능하다. 필자는 DFS를 이용했다. (미로 찾기처럼 뻗어나가는 문제는 DFS를 이용한 풀이를 좋아하는 편이다) 🗝 문제풀이 1. 높이가 0 ~ 100 범위일 때 안전한 지역을 찾고, DFS를 이용하여 안전 지역의 범위를 체크한다. ⚠️ 높이가 1 ~ 100 범위이기 때문에 h를 1로 둘 수 있는데 1부터 시작하게 되면 아무 지역도 물에 잠기지 않..

[알고리즘] 동전 교환 알고리즘

동전 교환 알고리즘 최소의 갯수로 거스름돈을 주는 방법에 대해 알아보자. 그리디 알고리즘 동전교환 문제를 풀기 위해 그리디 알고리즘을 사용할 수 있다. 하지만 그리디 알고리즘은 가장 적은 동전 수의 최적해를 항상 찾는 것은 아니다. 예를 들어보자, 동전의 종류가 [1, 3, 4] 이렇게 존재하고 9원을 거스름돈으로 준다고 하면, 그리디 알고리즘은 4원 1개, 3원 1개, 1원 2개를 선택할 것이다. 하지만 3원 3개를 거스름돈으로 주는 방식이 가장 적은 동전의 개수를 이용한 최적해이다. 그렇다면 항상 최적해를 찾기 위해 어떤 알고리즘을 이용해야 할까? DFS DFS 알고리즘을 이용할 수 있다. 위와 같이 [1,3,4] 동전 종류가 있고, 9원을 거스름돈으로 거슬러 준다고 해보자. 각 코인마다 3개의 가지..