백준
-
[백준] 16933 벽 부수고 이동하기 3Problem Solving/Baekjoon Online Judge 2020. 3. 24. 12:57
[문제이해] 1. NxM 으로 표현되는 map이 있다. (0은 이동할 수 있는 공간이고, 1은 이동할 수 없는 벽이다.) 2. 당신은 (1,1)에서 (N,M)위치로 최단 경로로 이동 해야한다. 3. 이 문제에는 낮과 밤이 존재한다. 가장 처음에 이동할 때는 낮이고, 이동할 때마다 낮과 밤이 바뀐다. 4. 이동하지 않고 같은 칸에 머무를 수 있는데, 이때도 낮과 밤이 바뀐다. 3. map에서 벽을 만나면, 벽을 부술 수 있다. (벽은 최대 k개 만큼 부술 수 있다.) 4. 단, 벽은 아침에만 부술 수 있다. 5. map이 주어지고 N, M, k가 주어졌을 때 최단 경로를 구해내야 한다. [설계] 1. 최단경로를 구하는 문제이므로 BFS를 사용하여 구현한다. 2. BFS로 방문하는 정점의 정보는 4가지이다...
-
[백준] 16197 두 동전Problem Solving/Baekjoon Online Judge 2020. 3. 8. 23:16
[문제이해] 1. N x M map에는 두 개의 동전(o) 벽(#)과 빈 칸(.)이 존재한다. (두 동전의 위치는 다름) 2. 두 동전을 동시에 움직일 수 있는 버튼이 있다. (방향은 상하좌우 4방향) 3. 두 동전 중 하나만 map에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구해야한다. 4. 단, 동전을 떨어뜨리거나 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다. [설계] 1. x,y 구조체에 대한 구조체를 만들어 두 동전의 위치좌표를 간단하게 표현한다. 2. 4 방향의 버튼을 누르는 경우의 수를 재귀적으로 구현한다. 3. 재귀단계가 10이 넘어가면, 실패 (-1 출력) 4. 한 개의 동전만 떨어졌을때 버튼을 누른 횟수가 최소인지 체크하고, 최소이면 값을 갱신한다. 5. 두 동전이 모..
-
[백준] 13460 구슬 탈출 2Problem Solving/Baekjoon Online Judge 2020. 3. 6. 19:23
[문제이해] 1. 맵에는 벽(#), 빨간구슬(R), 파란구슬(B), 구멍(O)이 각각 1개씩 존재한다. 2. 4가지 기울이기(왼쪽, 오른쪽, 위쪽, 아래쪽)를 통해 구슬을 굴릴 수 있다. - 빨간구슬이 구멍에 빠지면 성공 - 파란구슬이 구멍에 빠지면 실패 - 빨간구슬과 파란구슬 모두 구멍에 빠져도 실패 - 기울이기를 10번 초과하면 실패 3. 보드의 상태가 주어졌을 때 최소 몇 번만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지를 계산해야한다. [설계] 1. 빨간구슬과 파란구슬에 대해 상,하,좌,우 4방향 BFS를 적용한다. 2. 예를들어 맵을 오른쪽으로 기울였으면, 빨간구슬과 파란구슬 둘 다 오른쪽 방향 BFS를 적용한다. 3. 큐에다가 빨간구슬 x, y 좌표와 파란구슬 x, y 좌표 그리고 기울인 횟수 ..