Jonyo Programming

입력 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다. 출력 첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다. [BOJ 2589(G5) 리뷰] L은 땅이고 W는 바다이다. 바다로는 이동할 수 없으며 땅으로만 다닐 수 있다. 각 육지사이의 거리가 최대가 될때 그 두개의 육지에는 보물이 묻혀있다고 한다. 이때 그 육지사이의 거리가 최대가 되는 거리가 몇인지 출력하면 된다. 완전탐색을 이용해 풀었다. 존재하는 모든 육지에대해서 BFS를 수행하여 가장 거리가 멀때를 기록하고 존재하는 모든 육지에대..

입력 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다. 출력 첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다. [BOJ 1389(S1) 리뷰] 입력으로 친..

[BOJ 3055(G5) 리뷰] 이전에 풀었던 불! 문제와 비슷한 유형이다. 그때 썼던 코드를 거의 그대로 가져다 썼다. 먼저 물에대해 BFS를 수행하고 고슴도치에 대해 BFS를 수행하면 된다. #include #include #include #include #include #include #include #include #include using namespace std; #define X first #define Y second string board[1002]; int dist[1002][1002]; int dist2[1002][1002]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; int main(void) { cin.tie(0); ios::syn..

[BOJ : 13913(G4) 리뷰] 처음엔 접근방법이 어려웠다. 동생을 찾는것까지는 쉬운데 최단거리까지의 경로를 출력해야 한다. 현재 노드가 어떤 노드로부터 왔는지 기록하면 된다는 힌트를 보고 풀었다. BFS수행할때마다 이전노드를 기록하고, 마지막에 스택에 넣어 출력했다. #include #include #include #include #include #include #include #include #include using namespace std; int dist[200002]; int parent[200002]; int main(void) { cin.tie(0); ios::sync_with_stdio(0); int n, k; cin >> n >> k; queue Q; fill(dist, dist ..

[BOJ 6593(G4) 리뷰] 이전에 풀었던 토마토 문제와 굉장히 비슷하다. 3D배열을 이용해 풀면된다. #include #include #include #include #include #include #include #include #include #include using namespace std; #define X first #define Y second char board[32][32][32]; int dist[32][32][32]; int dx[6] = { 1,0,-1,0,0,0 }; int dy[6] = { 0,1,0,-1,0,0 }; int dz[6] = { 0,0,0,0,1,-1 }; int main(void) { cin.tie(0); ios::sync_with_stdio(0); whil..

[BOJ 5014(G5) 리뷰] 강호씨가 엘리베이터를 타고 특정층에 가려고 한다. 현재 강호씨의 위치와 강호씨가 가고자 하는 층이 주어지고 U와 D값이 주어지는데 위로 가는 버튼을 클릭하면 위로 U층을 가며 아래로 가는 버튼을 누르면 아래로 D층을 간다. 강호씨가 현재 위치에서 가고자 하는 위치까지 버튼을 총 몇번 눌러야 하는지 출력해야 한다. 전에 풀어봤던 문제와 비슷해서 쉽게 구현할 수 있었다. #include #include #include #include #include #include #include #include #include using namespace std; int elev[2000002]; int main(void) { cin.tie(0); ios::sync_with_stdio(0)..

입력 첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다. 출력 첫째 줄에 가장 짧은 다리의 길이를 출력한다. [BOJ 2146(G3) 리뷰] 지도에 여러섬이 존재한다. 각 섬에서 다른섬으로 가는 최단경로를 찾아야 한다. 나는 다음과 같이 풀었다. 1.인접한 영역이 같은 섬이므로 1차적으로 BFS를 수행해 각 섬마다 index를 부여했다. 2.(1,1)부터 (n,n)까지 모든 경우에 대해서 현재의 섬index에서 다른 섬의index까지 도달하는데 걸리는 거리의 최소값을 구했다. 모든 경우의 수에서 탐색을 진행하다보니 시간복잡도는 엄청나게 증가..

[BOJ 4179(G3) 리뷰] 지훈이가 미로에 갇혀있다. 미로에 불이나서 불이 1분에 한칸씩 옮겨간다고 한다. 지훈이도 1분에 한칸씩 이동할 수 있다. 주어진 미로에서 지훈이가 과연 탈출할 수 있는지 구하고 탈출한다면 가장 빨리 탈출하는데에 몇초가 걸리는지 구해야한다. 탈출하지 못하면 IMPOSSIBLE을 출력해야한다. 입력은 다음과 같이 주어진다. 4 4 #### #JF# #. .# #. .# 새로운 유형이라 접근방법이 굉장히 어려웠다. 힌트를 보고 풀었다. 문제를 풀기 위해선 먼저 불이 옮겨가는 시간에 대해 탐색을 수행해야 한다. 그 후에 지훈이의 위치로부터 탐색을 시작하자. 지훈이가 가고자하는 위치가 이미 먼저 불이 옮긴 위치라면 그곳으로 이동할 수 없다. 벽을 만나게되면 탈출에 성공한것이므로 거..

입력 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다. 출력 첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다. [BOJ 2584(G4) 리뷰] 쉬운듯 어려웠다. 빙산의 높이가 주어진다. 빙산은 주위에..

[BOJ 2206(G4) 리뷰] 진짜 어려웠던 문제.. 첨에 머리싸매고 아무리 고민해도 풀이가 안떠올랐다. 벽이 있을때랑 없을때랑 해서 어찌저찌 해볼려했지만 도저히 풀리지 않았고 3D배열을 사용한다는 힌트를 봤을때 그제서야 조금씩 코딩을 할 수 있었다. 이 문제의 핵심은 '1.벽을 한번도 부수지 않고 목적지에 도착하는 경우' 와 '2.벽을 한번 부수고 목적지에 도착하는 경우' 로 나누어 계산해야한다. 따라서 거리를 기록하는 배열을 기존 2D배열에서 3D배열로 확장하여 진행 했다. 로직은 다음과 같다. 시작점 (1,1)에 방문표시를 하고 BFS를 시작한다. 상,하,좌,우 네가지 방향에 대해 방문을 실시한다. 만약 BFS를 진행중에 벽이 나타났다면 현재까지 벽을 부순적이 있는지 없는지 확인하고 벽을 부순적이..