도지와 나

[백준] 19238.스타트 택시 (Swift) https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 BFS 를 이용한 최단거리 계산 문제입니다. 같은 거리에 있는 승객이 여러명이라면 행의 크기가 가장 작은 승객을, 그마저도 여러명이라면 열의 크기가 가장 작은 승객을 태우는 것이 문제의 조건입니다. 이를 해결하기 위해서 먼저 BFS 로 모든 승객과의 거리를 계산한 후에 최소거리에 있는 승객을 추려냈습니다. ..

[백준] 5014.스타트링크 (Swift) https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 시작층에서 목표층까지 도달하기 위해 버튼을 눌러야하는 최소 횟수를 구해야 합니다. 버튼은 위, 아래 2개가 존재하기 때문에 현재 있는 층에서 위로 가는 버튼을 누른다, 아래로 가는 버튼을 누른다 2가지 경우의 수를 생각해볼 수 있습니다. 이렇게 생각하면 간단하게 구현할 수 있을 것 같지만, 신경써야 하는 점이 크게 2가지가 있습니다. 이미 방문한 층에서는 어떤 ..

[프로그래머스] 가장 먼 노드 (Swift, Java) https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 1. BFS 일단 문제를 읽고 1번 노드와 모든 노드간의 거리를 구해야했기 때문에 가장 가까운 노드부터 탐색하는 BFS 를 이용해야겠다고 생각했습니다. 노드의 탐색은 BFS 를 이용하면 비교적 간단하게 구현할 수 있지만, 가장 먼 노드의 개수를 알아야 했기 때문에 노드간의 거리를 계산하는 것이 문제의 핵심이라고 생각했습니다. 2. 거리 계산 거리계산을 위해 각 노드마다 1..

[백준] 1976.여행 가자 (Swift, Java) https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 1. BFS 입력은 인접행렬로 표현된 그래프가 주어지고, 마지막 줄에는 방문할 노드들이 순서대로 주어집니다. 처음에는 단순히 방문한 노드들을 차례대로 2개씩 뽑아서 BFS 를 진행할 생각이었습니다. 최단 경로가 존재한다면 true 를 리턴하고, 존재하지 않는다면 false 를 리턴하는 방식으로 접근하면 된다고 생각했습니다. 하지만 m 번만..

[백준] 16197.두 동전 (Swift) https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 풀이 주어진 2차원 배열 위에서 최단 거리를 찾아야 하니 BFS 로 해결할 수 있는 문제입니다. 다만 일반적인 BFS 문제와 조금 다른 점은 2개의 포인트가 동시에 같은 방향으로 움직인다는 것입니다. 움직이는 동전 2개 중 오직 1개만 보드 밖으로 나가게 되거나 움직이는 횟수가 10 보다 커지면 BFS 는 종료되어야 합니다. 동전이 보드를 탈출하지 못하..