Jonyo Programming

[BOJ 2660(G5)리뷰] 주어진 관계를 이용해 BFS를 수행해 DEPTH를 기록하여 해결할 수 있는 문제다. 플로이드 문제를 풀려고 봤는데 BFS로 푸는게 더 간단할 것 같아 BFS로 풀었다. 주의해야 할 조건은 회원 사이에 친구를 통해서 모든 회원을 알 수 있다는 점이다. 즉, 각각의 회원은 자신을 제외한 모든 회원간의 DEPTH가 반드시 존재한다. 따라서 BFS를 돌며 각 회원간의 DEPTH를 기록하면 된다. 점수가 1점이라는 의미는 모든 회원간의 DEPTH가 1이라는 의미이고, 점수가 2점이라는 의미는 모든 회원 중 최대 깊이의 DEPTH가 2라는 의미이다. 그래서 나는 크게 '1. BFS를통해 회원간 DEPTH계산, 2.각 사람별 최대 DEPTH를 통한 점수계산 3.점수 중 최소값 계산하여 ..

[BOJ 1039(G3)리뷰] 굉장히 어려웠던 문제다. 처음엔 이걸 어떻게 BFS로 풀라는 건지 한참 고민을 했다. 계속 고민을 하다보니 그냥 모든 경우에 대하여 BFS를 돌리면 되는 간단한 문제인가? 라는 생각이 들어 바로 코딩을 했지만 계속 메모리초과&시간초과가 났다. 시간초과가 났던 이유는 너무나 당연했다. 두개의 값을 바꾸는 과정에서 중복되는 값이 큐에 푸쉬되는 현상이 반드시 일어 날 수있고, K가 클수록 시간복잡도 측면에서 매우 큰 손해를 보게 된다. 따라서 중복된 값을 큐에 넣지않도록 별도의 처리를 해줘야 한다. 다만 이때 각각의 연산마다 중복처리를 하는것을 독립적으로 계산해야 한다. 즉, 16375 에서 61375가 되고 다시 16375가 될 수 있는것이다. 각각의 연산횟수마다 독립적으로 처..

[BOJ 14500(G5) 리뷰] 삼성 SW역량테스트 기출문제다. 처음엔 엄청 간단한 문제인 줄 알았다. 그냥 DFS로 구현하면 쉽게 풀릴것같아 쓱 구현해서 돌려보니 문제가 발생했다. DFS로는 이 모양을 만족할 수가 없는것이였다. 어떻게 처리할까 매우 고민했다. 이왕 하는거 논리적이고 깔끔하게 코드를 짜고싶어서 머리를 이리저리 굴려보았는데 답이 잘 안나왔다. 계속 고민하다보니 집중력이 계속 떨어져서 그냥 무식한 방법을 사용하기로 했다. DFS를하면서 두번째 블록에 위치할때, 위 모양이 나올 수 있는 경우의 수를 생각해서 그냥 인덱스로 접근해서 구해버렸다. 그나마 순열로 구현하는게 깔끔할테지만, 넥퍼뮤 사용법도 까먹고해서.. 그냥 무식하게 구해버렸다. 어쨌든 맞았으니 기분은 좋긴한데 왠지모를 찝찝함이 남..

[BOJ 1963(G5) 리뷰] 네자리의 소수로 된 비밀번호를 다른 네자리의 소수로 바꾸려고 한다. 그러나 바꿀때는 한 자리씩 밖에 변경할 수 없고 한자리씩 바꾸었을때의 네자리 역시 소수여야 한다. 기존 비밀번호와 바꾸고자 하는 비밀번호가 주어질때 원하는 비밀번호까지 최소 몇번의 단계를 거쳐야 하는지 출력해야 하는 문제이다. 우리는 원하는 비밀번호까지의 최소 단계를 구해야 하므로 BFS로 접근해야 한다. BFS를 수행하기 전에 소수 확인 작업을 O(1)에 처리하기 위하여 먼저 1000~9999의 숫자에 대해 소수판별 작업을 거쳤다.그 후에 현재 비밀번호의 첫번재 자리부터 네번째 자리까지에 0~9의 수를 넣어보고 넣어봤을때의 숫자가 소수라면 큐에 넣고 이어서 탐색하도록 하면 된다. 처음엔 코드가 비효율적이..

입력 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다. 출력 첫째 줄에 원숭이의 동작수의 최솟값을 출력한다. 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다. [BOJ 1600(G5) 리뷰] 푸느라 혈압올랐던 문제.. 일단 첨에 문제 잘못이해하고 삽질 1시간 메모리 초과나서 +1시간 100%에서 틀렸다고 나와서 +1시간.. 거의 3시간이 걸렸고 결국 경계조건에 대해 예외처리를 해주고나서야 정답처리가 되었다. ..

입력 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 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..