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

입력 첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다. 0: 빈 칸 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기 9: 아기 상어의 위치 아기 상어는 공간에 한 마리 있다. 출력 첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다. [BOJ 16236(G5) 리뷰] 골드5문제라 간단한 BFS일줄 알았는데 은근 조건이 까다로워서 푸는데 애를 먹었다. BFS를통해 아기 상어가 먹을 수 있는 물고기의 거리를 재고, 가장 가까운 먹이를 먹어야 한다. 먹이를 먹을수록 아기 상어의 크기는 점점 ..

[BOJ 16234(G5) 리뷰] 풀고 나면 굉장히 간단한 문제인데, 풀기 전에는 왜이렇게 어려운지 모르겠다. 처음에 문제 이해하는게 좀 힘들었는데 문제를 잘 살펴보니 전형적인 BFS문제이다. BFS를 통해 국경선이 열리는 조건에 대해 확인을 한 후 만족하는 그룹을 하나의 연합으로 보면 된다. 처음에는 먼저 BFS를 수행하여 각 국가마다 연합 INDEX를 부여하고 연합INDEX를 토대로 BFS를 다시 수행하여 값을 바꿔주려고 했는데 굉장히 비효율적인 작업임을 알아챘다. 그래서 벡터를 만들어 처음 BFS를 수행할때 각 연합INDEX에 바뀌게 될 값을 저장하고, 반복문을 통하여 연합INDEX에 맞게 저장된 값으로 바꿔주는 작업을 수행했다. 결과적으로 다음과 같다. 1.numbering (각 국가에 대해 국경..

입력 첫째 줄에 정수 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 10025(G5) 리뷰] RGB색상이 주어지는데 적록색약은 빨간색과 초록색을 구분하지 못한다고 한다. 각각의 색깔이 구분되는 구역의 수를 세야한다. 정상인은 세가지 색에 대해 구분을 할 수 있지만 적록색약은 빨간색과 초록색을 한가지 색으로 구분하게 된다. 이 때 정상인이 바라보는 구역과 적록색약이 바라보는 구역의 수를 각각 출력하면된다. 한번의 연산만으로 수행할 수 있을까싶어 머리를 굴려봤지만 아이디어가 떠오르지 않았다. 그래서 그냥 BFS를 정상인의 경우와 적록색약의 경우로 나누어 탐색하여 결과값을 출력했다. 1= n) continue; if (check[nx][ny] != '0' || board[nx][ny] != color) continue; check[nx][ny] = color; Q.p..