[C++] 벽 부수고 이동하기 (2206번)

벽 부수고 이동하기 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다...

• format_list_bulleted 알고리즘(Algorithm)
• · 2022. 10. 18.
• textsms

[C++] 아기 상어 2 (17086번)

아기 상어 2 문제 N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다. 어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는 하나의 칸에서 다른 칸으로 가기 위해서 지나야 하는 칸의 수이고, 이동은 인접한 8방향(대각선 포함)이 가능하다. 안전거리가 가장 큰 칸을 구해보자. 입력 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈칸, 1은 아기 상어가 있는 칸이다. 빈칸과 상어의 수가 각각 한 개 이상인 입력만 주어진다. 문제풀이 접근 방법에 대해 고민을 조금 많이 했다. 우선 모든 아기 ..

• format_list_bulleted 알고리즘(Algorithm)
• · 2022. 10. 14.
• textsms

[C++] 트럭 (13335번)

트럭 문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다. 예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭..

• format_list_bulleted 알고리즘(Algorithm)
• · 2022. 10. 14.
• textsms

[C++] 백준 파이프 옮기기1 (17070번)

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이프 옮기기 1 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프..

• format_list_bulleted 알고리즘(Algorithm)
• · 2022. 10. 13.
• textsms

[C++] 플로이드 와샬 (Floyd-Warshall Algorithm)

Floyd-Warshall 플로이드 알고리즘, 로이-와샬 알고리즘, 로이-플로이드 알고리즘, WIFI 알고리즘 등으로 불린다. 그래프에서 최단경로를 찾는 문제를 해결하는 알고리즘의 한 종류이다. 다익스트라 알고리즘의 경우 가중치가 양수이고, 하나의 시작점으로부터 다른 모든 버텍스(vertex, node, 노드)까지의 최소 비용을 구한다. 플로이드 와샬은 이 다익스트라를 여러 번 행하여 모든 버텍스에서 다른 모든 버텍스까지의 경로를 구하는 알고리즘이다. 시간 복잡도는 O(n^3)이다. 이론적으로 이해하는 데에는 시간이 조금 걸리지만 코드는 그냥 반복문 세 개 갖다 쓰는 거라 매우 간단하다. 이론 현재 나의 위치가 i이고, j까지 가는 최단경로를 알고 싶다. i에서 j로 한 번에 가지는 경우가 최단거리 일 ..

• format_list_bulleted 알고리즘(Algorithm)
• · 2022. 8. 28.
• textsms

백준 2638 치즈 C++ [골드3]

문제 N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다. 와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, ..

• format_list_bulleted 알고리즘(Algorithm)
• · 2022. 8. 7.
• textsms