설모의 기록

이 문제는 4개짜리 테트로미노 블럭을 주어진 이차원 배열에 놨을 때 배열의 값의 합이 최대가 되는 값을 구하는 문제입니다. 폴리오미노의 조건은 아래와 같습니다.정사각형은 서로 겹치면 안된다.도형은 모두 연결되어 있어야 한다.정사각형의 꼭지점끼리 연결되어 있어야 한다. 즉, 변과 꼭지점이 맞닿아 있으면 안된다.이 때, 정사각형 4개를 이어붙인 폴리오미노를 테트로미노라 하고 아래의 그림과 같이 5가지 종류입니다. 저도 처음에는 '5개를 어떻게 회전하지.. 4*4배열을 생성해서 그 배열을 회전해야하나..' 하는 함정에 빠졌습니다. 이것을 어떻게 해결하냐가 관건입니다. 이 문제는 dfs로 간단하게 풀리는 문제입니다. 'ㅜ' 블럭을 제외한 4개의 블럭은 한번에 그릴 수 있죠? 다시 말하면 dfs로 한번에 탐색할 ..

이 문제는 그냥 나눗셈만 하면 되는 간단한 문제였습니다. 다만 int 가 32bit 이기 때문에 각 시험장에 백만명씩 있고 총감독관과 부감독관이 감시할 수 있는 응시자 수가 1이라면 범위를 벗어나겠죠? 따라서 감독관 인원수를 담을 변수는 int 가 아닌 long으로 선언해야 합니다. 단위만 조심하면 정말 쉬운 문제입니다!

이 문제는 벽 3개를 추가한 후 바이러스가 퍼졌을 때의 안전구역의 최대값을 구하는 문제입니다. 저는 재귀함수와 bfs를 이용했습니다. 제 규칙은 아래와 같습니다.재귀함수를 이용해 벽 3개 구하기초기 배열을 cloneMap에 복사하고 구한 3개의 벽도 추가bfs를 수행하며 바이러스를 퍼트린 후 안전영역 개수 구하기 위의 규칙을 토대로, 먼저 N, M, map 세개를 입력받고 나중에 안전구역 영역을 셀 때 또 이중반복문을 수행하지 않기 위해 안전구역갯수(safeAreaCount)를 저장했습니다. 그리고 N*M 만큼 for문을 반복해 이중for문을 피했습니다. 일단 벽 하나를 세운 뒤 recursive 함수를 호출해 벽 2개를 더 세우고 안전구역 영역을 구합니다. private static void recur..

이 문제는 로봇청소기가 map을 돌아다니며 얼마만큼의 영역을 청소하는지를 구하는 문제입니다. 로봇청소기가 돌아다니는 조건은 아래와 같습니다. 현재 위치를 청소한다.현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 수행한다.왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다. 이 문제는 전형적인 dfs 문제입니다. 우선 제가 생각..

이 문제는 높이 차이가 1이고 L만큼 평평한 곳에 경사로를 설치하는 문제입니다. map 그림만 보고 dfs, bfs 문제라고 예상했는데 그냥 이중포문 문제였네요! 위의 그림과 같은 땅이 있을 때, L = 2 라고 주어졌습니다. 높이가 차이나는 곳은 그 차이가 1이여야 하며, 주어진 조건에 맞게 경사로를 설치할 수 있어야 합니다. 그림에서는 초록색으로 표시한 부분이 지나갈 수 있는 길입니다.길은 가로와 세로만 생각하면 되니까 편하게 배열 두 개를 선언하고 i, j 만 바꿔서 저장한 후에 똑같은 로직을 사용했습니다. checkBuild 함수에서는 받은 배열의 index 에 저장된 길이 지나갈 수 있는지를 확인합니다. 지나갈 수 없다면 return을, 지나갈 수 있다면 result에 +1 을 하는 방식입니다...

이 문제는 4개의 톱니바퀴가 연쇄적으로 회전한 후의 점수를 산출하는 문제입니다. 4개의 톱니바퀴는 각각 8개의 톱니를 갖고 있으며 N 또는 S극입니다. 하나의 톱니바퀴를 회전하면 위의 그림과 같이 다른 톱니와 맞닿아 있는 부분이 다른 양 옆의 톱니도 반대방향으로 회전하고, 그 톱니들의 양 옆도 맞닿아 있는 부분이 다르다면 연쇄적으로 회전을 하게 됩니다. 그림이 어지럽게 그려져서 그렇지, LinkedList로 생각하면 쉽습니다. 시계방향으로 회전하는 것은 리스트의 마지막 요소를 뺴와 첫번째 인덱스에 추가하는 것이고, 반시계방향으로 회전하는 것은 리스트의 첫번째 요소를 빼와 마지막에 추가하는 것과 같습니다. 그리고 회전하기 전에 각각의 톱니바퀴가 양 옆의 톱니바퀴와 맞닿아 있는 곳이 같은지를 체크해주고, 회..