Jonyo Programming

입력 첫째 줄에 공간의 크기 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 (각 국가에 대해 국경..

[BOJ 14502(G5) 리뷰] 연구소에 벽을 3개 설치할 수 있다. 벽을 설치한 후에 연구실에 있는 바이러스는 빈 공간으로 퍼져 나간다. 벽으로 막혀있다면 더 이상 퍼져나가지 않는다. 연구소에 벽을 3개 설치하는 경우 중에서 가장 적게 바이러스가 퍼질때 바이러스가 퍼지지않는 칸의 개수를 구하는 문제이다. 백트래킹+BFS로 문제를 해결했다. 먼저 벽을 3개 세우는 경우를 백트래킹을 통해 하나씩 확인해주고, 각각의 경우에 대해 BFS를 수행하여 바이러스가 퍼지게 한 다음 바이러스가 퍼지지 않는 공간의 갯수를 세면 된다. 시간초과를 걱정하며 문제를 풀었는데 채점TC가 느슨해서인지 정답은 나왔지만 예제에 나온 테스트케이스는 제시간에 답이 안나왔다. 조합을 사용하여 최대한 속도를 줄였지만 그래도 맵은 크고 초..

[BOJ 3190(G5) 리뷰] snake 게임을 해본적이 있을것이다. 뱀을 조종하여 사과를 먹게되면 뱀의 길이가 점점 늘어난다. 뱀이 벽에 부딪히거나 자기 몸에 부딪힌다면 게임은 끝나게 된다. 이 문제는 snake게임의 규칙을 그대로 따른다. 맵이 주어지고 사과의 위치가 주어진다. 뱀은 주어진 명령대로 이동을하다가 사과를 만나면 길이가 늘어난다. 주어진 명령에 따라 게임을 수행했을 때 몇초후에 게임이 종료되는지를 구하는 문제이다. 일단 명령은 큐로받았다. 뱀을 이동시키기전에 큐의 front를 확인하여 현재 소요된 시간과 명령시간을 비교하여 명령에 맞게 방향을 바꿔주도록 했다. 그다음 시간이 지나면서 뱀을 이동시키고, 사과를 먹으면 길이를 늘려주면된다. 이 때 길이를 늘려주는 작업이 조금 헷갈렸다. 처음..

[BOJ 14891(S1) 리뷰] 톱니바퀴 문제. 입력으로 톱니바퀴의 번호와 방향이 주어진다. 톱니바퀴가 돌때 양 옆에있는 톱니바퀴와 맞닿아 있는 부분이 서로 다른 극이라면 옆에 있는 톱니바퀴도 회전하게 된다. 만약 옆에있는 톱니바퀴가 회전하며 또 다른 톱니바퀴와 다른 극 이라면 그 톱니바퀴도 회전해야 한다. 주의해야할 점은 톱니바퀴를 회전시키기 전에 미리 양 옆에 있는 톱니바퀴와 확인을 해준 후 회전시켜야 한다. 회전하는 톱니바퀴 각각에 대해 양 옆의 톱니바퀴를 확인해줘야하므로 재귀함수를 사용했고 이미 회전한 톱니바퀴는 다시 회전하지 않도록 하기 위해 isUsed배열을 사용했다. 처음엔 구현이 막막했는데 그냥 각각의 톱니바퀴에 대해 일일히 index로 접근해 확인하는 방법을 택했다. #include #..

[BOJ 11559(G5) 리뷰] 뿌요뿌요 문제다. 같은색의 뿌요가 4개인접해있으면 그 뿌요들은 터지며 없어진다. (애니팡과 비슷) 뿌요가 터지면 위에있는 뿌요들은 아래로 모두 내려오게 되며 아래로 내려왔을때 4개이상 인접해있는 뿌요가 있다면 또 터지게 된다. 이 때 연속적으로 몇번의 차례동안 뿌요가 터지는지 계산하는 문제이다. 애니팡을 해봤으면 하나를 터트렸을때 터진자리에 새로운 캐릭터가 채워지면서 연쇄적으로 터지는걸 경험한적이 있을것이다. 그걸 생각하며 구현하면 된다. 같은색의 뿌요를 찾는 BFS와 뿌요가 터진 후 뿌요들을 아래로 내려주는 함수를 구현하면 된다. #include #include #include #include #include #include #include #include #inclu..

입력 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마지막 줄에는 이동하는 명령이 순서대로 주어진다. 동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4로 주어진다. 출력 이동할 때마다 주사위의 윗 면에 쓰여 있는 수를 출력한다. 만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도..

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 출력 첫째 줄에 사각 지대의 최소 크기를 출력한다. [BOJ 15683 (G5) 리뷰] 문제가 드럽게 길다..; 그런데 문제가 길다는것은 그만큼 설명을 자세하게 해준다는것. 정확히 뭘 구현해야하는지 제시해주고 있다. 사각지대의 최소 크기를 구해야하므로 백트래킹을 이용..

입력 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다. 둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다. 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다. 출력 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다. [BOJ 15686 (G5) 리뷰] 처음에 문제 이해가 잘 안돼서 여러번 읽었다. 집과 치킨집과의 거리를 치킨거리라고 하는데 주어진 치킨집의 개수를 만족하며 존재하는 집의 치킨거리의 합이 최소가 되는경우를 구하면 된다. 모든경우를 탐색해야하므로 백트래킹을 ..

[BOJ 1987(G4) 리뷰] 후... 엄청나게 힘들었던 문제다. 처음엔 문제 잘못읽고 BFS로 접근했다. 코딩 다했는데 그제서야 문제 제대로 이해하고 싹 갈아엎었다. 처음엔 set을 통해 문자를 하나하나씩 쌓으면서 중복된게 있는지 비교했는데, 처음에 백트래킹하면서 쌓아놓았던 문자를 제거하지 않아서 틀렸다. 이걸 수정하고 제출했더니 set때문인지 시간초과가 나왔다. 그래서 인터넷을 참고해 중복된걸 확인하는것을 A~Z까지 배열에 담아 O(1)로 확인했더니 통과되었다. 후.. 2시간은 넘게 걸린거같다. #include #include #include #include using namespace std; char board[21][21]; bool isUsed[21][21]; int dx[4] = { 1,-..