열심히해보겠씁니다

A -> B 로 가는 최소비용을 구하면 된다. A -> B 로 갈 수 있는 경우만 입력으로 주어진다는 조건이 있으므로 최소 비용 구하는 것만 신경쓰면 된다. 여기서 버스 비용은 0 이상이므로 버스를 이용할수록 손해이므로 버스는 최대 N-1 번 이용할 것이고, 한 번 타는데 최대 비용은 10^5 이고 N 은 10^3 이므로 최대 나올 수 있는 비용은 10^8 이므로 int 로 처리한다. #include #include #include #include using namespace std; int N, M, s, e, c; int start_city, end_city; vector edge[1001];//[도시번호] pair(비용,다음도시) int dijkstra(int start_city, int end_c..

스마트하고 그리디한 택시기사를 위한 문제이다. 문제의 조건은 다음과 같다. 1. 가장 가까운 승객을 태운다.(여러명일 경우 y가 가장 작은 승객, y가 같은 경우 x가 가장 작은 승객을 먼저 태운다) 2. 승객을 목적지 까지 태워준다. 3. 연료는 1칸 이동할때마다 1씩 닳는다. 4-1. 승객에 도착하기 전 연료가 다하거나 목적지에 도착하기 전 연료가 다하면 -1을 출력한다. 4-2. 승객을 모두 태우기 전에 종료되면 -1을 출력한다. 5. 도착지에 도착하면, 승객을 태운 위치에서부터 걸린 시간(이동한 칸 수)의 2배만큼의 연료를 충전한다. 6. 모두 태우고 나서 남은 연료의 양을 출력한다. 7. 벽은 지나가지 못한다. 문제의 접근 방식 및 해결방식은 다음과 같다. 1. 가장 가까운 승객을 찾는다.(BF..

구슬탈출 1과 유사하지만 살짝 다른점이 있는 문제이다. 컴퓨터스러운 문제에서 현실 세계 시뮬레이션 문제로 바뀐 듯한 느낌이다. 조건은 다음과 같다. 1. 구멍에는 빨간 구슬만 들어가야한다.(빨간 구슬이 들어간 후 파란 구슬이 들어가도 실패) 2. 10회를 초과해야하거나 초과해도 못들어가는 경우는 실패로 간주한다. 3. 구슬은 부딪혀도 상관없지만, 온전한 1칸을 차지하기 때문에 옆에 구슬이 있다면 더 이상 가지 못한다. 4. 구슬은 멈출 때(벽을 만나거나 다른 구슬을 만나거나 구멍에 들어갈 때) 까지 굴러간다. 문제 풀이는 간단하다. BFS를 사용하여 빨간 구슬과 파란 구슬의 위치를 발전시켜나가면 된다. 하지만 중복되는 상태를 고려하지 않으면 무한 루프가 생기게 되므로 visit 배열을 4차원 [Ry][R..

눈물나는 견우와 직녀의 일화이다. 하필이면 절벽지대에 살아가지고 오작교가 없으면 서로가 만나지 못할 수도 있다. 문제의 조건은 다음과 같다. 1. 한 칸을 이동하는데 1분이 걸린다. 2. 오작교에 적힌 시간의 배수에만 (0포함) 견우가 다리를 건널 수 있다. 3. 절벽이 교차하는 곳에는 오작교를 놓을 수 없다. 4. 오작교는 연속으로 건널 수 없다. 이토록 많은 조건을 뚫고도 견우가 직녀를 만나러 갈 수 있을까? 문제 풀이의 청사진은 다음과 같다. 1. 가장 빨리 도착하는 경우를 구해야하므로 BFS 를 이용하여 경로를 찾아본다. 2. 시간복잡도는 정확하게 계산하기 어렵고, 이럴 일도 없지만 N*N (map의 크기) * N * N (0이 들어갈 경우) * N * N( 완전탐색) = 1백만이므로 여유가 차고..

모래성 문제. 모래성에 파도가 치는데, 모래성이 감당할 수 있는 것보다 큰 파도를 만나면 모래성이 무너진다. 얼마나 많은 시간이 지나야 모래성의 모습이 더이상 변하지 않을까? 우선 특수한 경우가 어떤 것이지부터 파악했다. 1. 가장자리에는 모래성이 없다. 2. 튼튼함이 9인 경우 반드시 무너지지 않는다. 3. 맵의 크기가 백만이므로 완전탐색으로 풀 수 없다. 이 세 가지를 이용해 코드의 방향과 최적화를 잡을 수 있을 것으로 기대한다. 우선 가장 빨리 결과에 도착하는 시간을 찾는 것이기 때문에 BFS 를 생각했다. 맵의 크기가 너무 크기도 해서 DFS 로는 시간 초과가 뜰 것이 분명했기 때문이다. 풀이 방식은 다음과 같다. 1. 초기 상태에서 무너질 수 있는 곳의 좌표를 찾아서 저장한다. 2. 무너질 수 ..

이 문제는 처음 접근 방식이 중요하다. 결론부터 말하자면 BFS를 이용해 접근하는 것이 가장 효율적인 것으로 생각된다. 하지만 처음 접근할 때는 홈페이지에 있는 예시만 보고 접근했기 때문에 반례들을 생각 못하고 무작정 짰다. 내 가장 큰 습관 중 하나는, 문제를 보고 원리가 파악된다면 그걸 '그대로' 구현하려고 한다는 것이다. 예를 들어서, 줄 가장 뒤에 있는 아이를 맨 앞으로 보냈을 때 최종 순위가 어떻게 되는가? 하는 문제가 있다면 당연히 가장 뒤에 있는 아이를 앞에 아이와 SWAP을 모두 한 후 출력하면 된다고 접근할 것이다. 하지만 조금 더 빠른 동작을 위해서 각 아이들의 순위를 모두 +1하고 가장 뒤의 아이만 1로 만들어도 충분할 것이다. 먼저 생각해볼만한 것은, 1. 이분 그룹은 유일하지 않다..

해당 문제는 Breadth-first-search(BFS) 방식으로 풀었다. 문제는 c언어로 해결하려할 시 BFS에 거의 필수적인 queue 를 구현해야한다는 것이었다. 근데 거기까진 아직 안배우고 익혀보지 않았기 때문에 우선 문제풀이를 위해 c++ 의 라이브러리를 이용해 문제 해결에 집중했다. BFS 방식은 너비우선탐색으로 가장 기초적인 탐색법으로 많은 경우에 사용된다. 특히 가장 빨리 탈출하는 문제에 특화되어 있는데, 내가 서있는 위치 기준으로 몇 번만에 목표지점까지 이동할 수 있느냐를 구하는데 아주 유용하다. BFS 의 작동 방식은 위의 그림과 같다. 현재 위치 기준으로, 과거에 방문하지 않은 곳, 갈 수 있는 곳을 기준으로 점차 넓혀가며 탐색한다. 이 때도 2가지 방식이 있는데, 만약 내가 END..