https://www.acmicpc.net/problem/16166 16166번: 서울의 지하철 서울의 지하철 노선은 총 3개이다. 1호선에는 0, 2, 3번 역이 있고, 2호선에는 2, 5, 7, 10번 역이 있고, 3호선에는 10, 8번 역이 있다. 출발역인 0번 역에서 8번 역으로 가는 최소 환승 회수는 (호선, 역) www.acmicpc.net 풀이 방법 BFS 를 사용하여 구현하였다. 문제의 메모리 제한이 128MB = 2^27 인데 역 번호는 2^32 - 1 이하의 정수로 무작위 입력되므로 BFS 구현 시 visited 배열을 역 번호 크기만큼 선언해줄 수 없다. 이를 해결할 방법을 생각해야 한다. 역은 (최대 호선의 개수 x 최대 역의 개수) = 10 x 10 하여 최대 100개의 다른 번호..
BFS
https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 풀이 방법 주사위를 굴릴 때의 규칙성을 찾아 주사위 이동을 구현하는 것이 가장 관건인 문제이다. 주사위 굴리기 구현에 대한 자세한 설명은 아래 14499 주사위 굴리기 문제를 참고한다. https://lhyeinlog.tistory.com/24 백준 14499 주사위 굴리기 자바(java) https://www.acmicpc.net/problem/14499 14499번: 주사위 ..
https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 방법 DFS + 백트래킹을 이용하여 풀었다. DFS 시 방문 체크는 빨간 구슬 좌표와 파란 구슬 좌표를 인덱스로 하는 4차원 배열 visited 을 선언해주었다. 풀이 흐름은 아래와 같다. 1. 현재 기울이는 방향대로 구슬을 이동시키는데, 이때 다른 구슬은 신경쓰지 않고 벽까지 이동시킨다. 2. 이동 후의 두 구슬이 같은 칸에 위치한다면 위치..
https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 방법 최소 시간, 즉 최단 거리를 구하는 문제이므로 BFS를 사용한다. 물 이동을 위해 물이 있는 칸의 좌표가 필요하므로 좌표들을 따로 water 큐에 저장하여 관리하였다. 1. 큐에 고슴도치가 있는 S칸의 좌표와 시간 배열 [x, y, t] 을 삽입한다. (처음 시간 t는 0이다.) 2. 물을 이동시킨다. 현재 물이 차있는 지역의 좌표를 water 큐에서 꺼내어 인접한 비어있는 칸을 물로 변경한 후 변..
https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 방법 구현, 시뮬레이션 문제로 주어진 문제 조건에 따라 먼저 승객을 고르고, 고른 승객을 목적지로 데려다 주는 것을 승객 수만큼 반복하면 된다. 택시와 승객은 각각 Taxi, Person 클래스를 만들어 객체로 관리하고 입력 받은 승객 정보는 Person 객체를 만들어 승객 번호를 인덱스로 하는 Person 객체 배열에 저장한다. 승객이 서있는 칸을 기..
