본문 바로가기

DFS

 (17)
[백준 / BOJ] 1103 게임 문제 출처 : https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 형택이는 1~9까지의 숫자와 구멍이 있는 직사각형 보드에서 게임을 한다. 보드의 1,1위치에 동전을 하나 올려놓고, 동전을 다음과 같이 움직인다. - 동전이 놓인 위치에 있는 숫자만큼 위,아래,왼쪽,오른쪽 위치로 움직인다. (이 과정에서 구멍은 무시한다.) - 동전이 이동한 위치에 구멍이 있거나 동전이 보드 밖으로 나가면 게임이 종료된다. 형택이가 동전을 최대 몇번 움직일 수 있는지..
[백준 / BOJ] 2638 치즈 문제 출처 : www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net N*M크기의 모눈종이에 치즈가 있다. 모눈종이의 가장자리부터 공기가 들어오는데, 공기에 2면 접촉해있는 치즈는 1초후 녹기시작한다. 가장자리에는 치즈가없을때, 모든 치즈가 녹아 없어지는데 걸리는 정확한 시간을 구하는 문제다. 풀이 BFS,DFS를 이용한 시뮬레이션 문제다. N,M이 최대 100,100이라서 총 칸수가 10000칸 까지 갈수있다. 한번 치즈를 녹일때마다 모든 칸을 다 봐준다..
[백준 / BOJ] 16724 피리 부는 사나이 문제 출처 : www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net N*M지도가 있고, 그 위에 영과일 회원들이 있다. 지도의 각 칸에는 U,D,L,R 이 쓰여있는데, (순서대로 위, 아래, 왼쪽, 오른쪽) 성우가 피리를 불기 시작하면, 영과일 회원은 자기 발 아래의 방향에 맞게 이동한다. 재훈이는 영과일 회원의 안전을 위해 SAFE ZONE을 설치할려고한다. 영과일 회원이 어디에 있던지 항상 SAFE ZONE으로 들어갈수있도록..
[백준 / BOJ] 14699 관악산 등반 - Swift 문제 출처 : www.acmicpc.net/problem/14699 14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net N개의 쉼터가 있고, 쉼터둘을 연결하는 M개의 도로가 있다. 각 쉼터에는 높이가 있으며, 항상 현재쉼터보다 높은위치로만 갈수있다고할때, 각 쉼터에서 최대한으로 방문할수있는 쉼터의 갯수를 구하는 문제다. 풀이 전에 풀었던 Dp+DFS문제인 욕심쟁이 판다 : www.acmicpc.net/problem/1937 와 비슷한 유형?의 문제라고 생각했다 *항상 현재 쉼터 보다 높은 쉼터로만 ..
[백준 / BOJ] 1405미친로봇 문제 출처 : www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자�� www.acmicpc.net 로봇이 동, 서, 남, 북 4방향으로 N번 이동한다. N번 이동했을때, 방문한 지점을 한번 더 방문했다면 경로가 복잡하다고 하고, 아니라면 경로가 간단하다고 한다. 각 방향에 대한 확률과 이동하는 횟수가 주어졌을때, 로봇의 이동경로가 간단할 확률을 구하는 문제다. 풀이 DFS와 백트래킹으로 풀었다. 처음에는 입력받은 동, 서, 남, 북 만큼 전부 저장해주고 (25 25 25 25를 입력받으..
[백준 / BOJ] 2611 자동차 경주 문제 출처 : www.acmicpc.net/problem/2611 2611번: 자동차경주 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어 www.acmicpc.net N개의 지점이 있는 그래프가 주어진다. 각 지점사이를 연결하는 도로에는 그 도로를 지날때 얻는 점수가 있다. 1번지점에서 출발해서 다시 1번지점으로 돌아올때, 가장 많이 얻을수있는 점수와, 그때의 경로를 출력하는 문제다. 도로는 단방향 이다. 풀이 dp배열에 (dp[idx] = idx까지 도착했을때 얻은 최대 점수) 를 저장해준다. DFS를 돌리며, dp[현재 도로에 도착했을때 까지 얻은..
[백준 / BOJ] 1113 수영장 만들기 문제 출처 : www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net N*M크기의 칸에 수영장을 만들려고 한다. 각 칸에 그 땅이 갖고있는 높이가 주어졌을때, 수영장에 물을 얼만큼 넣을수있는지 구하는 문제이다. 만약 수영장이 다음과 같다면, 16661 61116 16661 가운데 3개의칸에 5씩 넣어서 총 15만큼의 물을 넣을수있다. 만약 5보다 더 많이 넣는다면 수영장 벽의 높이인 6보다 커져서 물이 넘친다. 풀이 한달전에 풀었던 문제였다...
[백준 / BOJ] 6118 숨바꼭질 문제 출처 : www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

티스토리툴바