본문 바로가기

알고리즘 (2020 : 08 : 10 ~ )/BFS,DFS

 (22)
[백준 / BOJ] 1405미친로봇 문제 출처 : www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자�� www.acmicpc.net 로봇이 동, 서, 남, 북 4방향으로 N번 이동한다. N번 이동했을때, 방문한 지점을 한번 더 방문했다면 경로가 복잡하다고 하고, 아니라면 경로가 간단하다고 한다. 각 방향에 대한 확률과 이동하는 횟수가 주어졌을때, 로봇의 이동경로가 간단할 확률을 구하는 문제다. 풀이 DFS와 백트래킹으로 풀었다. 처음에는 입력받은 동, 서, 남, 북 만큼 전부 저장해주고 (25 25 25 25를 입력받으..
[백준 / BOJ] 6146 신아를 만나러 문제 출처 : www.acmicpc.net/problem/6146 6146번: 신아를 만나러 키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. www.acmicpc.net 키파는 신아에게 가야한다. 키파와 신아 사이에는 웅덩이가있고, 키파는 웅덩이를 피해서 가야한다.(키파가 신아에게 못가는경우는없다.) 키파의 위치는 항상 (0,0이고) 신아는 (-500~500, -500~500) 사이에 있다 키파는 상하좌우로만 움직일수있다. 풀이 BFS로 풀리는 문제였다. -500~500까지 가능하므로 전체 칸의 갯수는 1000 * 1000 = 1000000개..
[백준 / BOJ] 13931 숨바꼭질 4 문제 출처 : www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 수빈이와 동생은 숨바꼭질을 한다. 수빈는 자신의 위치에서 -1, +1, *2만큼 이동할수있다. 수빈이가 동생을 가장빨리 찾는 시간을 구하는 문제다. 풀이 BFS를 통해 푸는 문제였다. 배열을 이용해 자신의 전 위치를 체크해줘야하는데, 예를들어, 배열이 par[100005]로 선언되어있고 수빈이가 동생에게 가는 경로가 5 10 20 40 이라면, par[40]..
[백준 / BOJ] 1194 달이 차오른다, 가자. 제목 출처 : www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 민식이는 달이 차오르는 기회를 놓치지 않기 위해서 미로를 탈출하려고 한다. 한번 움직일때마다 수평 혹은 수직으로 한칸 움직일수있다. 민식이가 미로를 탈출하는데 걸리는 최소한의 이동횟수를 구하는 문제다. 미로에는 문이있고, 미로는 다음과 같이 구성되어있다. 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨) 벽 : 절대 이동할 수 없다. (‘#’) 열쇠 : 언제나 ..
[백준 / 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] 2206 벽 부수고 이동하기 문제 출처 : www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net N*M행렬이 주어진다. 이때, 이동할수있는곳은 0 벽이있어서 이동할수 없는곳은 1로 표시된다. 이동할때 벽을 최대 1회 부수고 이동할수있는데, 1,1에서 시작해서 N,M에 도달했을때 최단경로를 구하는 문제다. 풀이 BFS문제다. 일반적인 BFS와 check배열을 선언하는게 다른데, 3차원 체크배열을 선언해서 해당 지점에 벽을 부수고 이동한 경로와 최솟값과 벽을 부수지 ..

티스토리툴바