1. 암호 만들기
1) 문제
문제 설명
바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.
새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.출력
각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <climits> #include <algorithm> #include <iostream> using namespace std; int L,C; string cList = ""; string vowels ="aeiou"; vector<int> cListVisited; int vowelCnt = 0; bool isVowel(char c) { if (find(vowels.begin(), vowels.end(), c) != vowels.end()) return true; return false; } void dfs(int index, string password, int ccnt, int vcnt) { if (password.size() == L) { if (ccnt < 2) return; if (vcnt < 1) return; cout << password << '\n'; return; } for (int i = index; i<cList.size(); i++) { if (cListVisited[i]) continue; if (*(password.end()-1) > cList[i]) continue; cListVisited[i] = true; if (isVowel(cList[i])) dfs(index + 1, password + cList[i], ccnt, vcnt+1); else dfs(index + 1, password + cList[i], ccnt+1, vcnt); cListVisited[i] = false; } } int main() { cin >> L >> C; while(C--) { char temp; cin>>temp; cList += temp; } sort(cList.begin(), cList.end()); cListVisited.resize(cList.size(),false); dfs(0, "", 0, 0); return 0; }
2.. 감시
1) 문제
문제 설명
CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0
위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #
사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.입력
첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.
CCTV의 최대 개수는 8개를 넘지 않는다.
출력
첫째 줄에 사각 지대의 최소 크기를 출력한다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <climits> #include <iostream> using namespace std; struct CCTV { int _x; int _y; int _type; vector<pair<int,int>> rotVec; }; int N,M; int cnt = 0; int answer = INT_MAX; vector<CCTV> cctvVec; vector<vector<int>> board; vector<int> rotCntVec = {0,4,2,4,4,1}; vector<vector<pair<int,int>>> rotVecs = { {}, {{0, 1}}, {{0, 1}, {0, -1}}, {{0, 1}, {-1, 0}}, {{0, 1}, {0, -1}, {-1, 0}}, {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}, }; int CalcBlindSpot(int index, vector<vector<int>> inboard) { int res = cnt; for (int i =0; i < cctvVec.size(); i++) { auto current_cctv = cctvVec[i]; for (int j=0; j<current_cctv.rotVec.size(); j++) { int x = current_cctv._x; int y = current_cctv._y; while (true) { int nx = x + current_cctv.rotVec[j].first; int ny = y + current_cctv.rotVec[j].second; if (nx < 0 || nx >= N) break; if (ny < 0 || ny >= M) break; if (inboard[nx][ny] == 6)break; if (inboard[nx][ny] == 0) { inboard[nx][ny] = -1; res--; } x = nx; y = ny; } } } return res; } void RotateVec(CCTV& ctv, int cnt) { if (cnt == 0) return; int clockwise = cnt > 0 ? 0 : 1; for (int i=0; i<abs(cnt); i++) { for (int j = 0; j < ctv.rotVec.size(); j++) { int x = ctv.rotVec[j].first; int y = ctv.rotVec[j].second; if (cnt > 0) { // 시계 방향 90도 ctv.rotVec[j].first = y; ctv.rotVec[j].second = -x; } else { // 반시계 방향 90도 ctv.rotVec[j].first = -y; ctv.rotVec[j].second = x; } } } } void dfs(int index) { if (index == cctvVec.size()) { int res = CalcBlindSpot(index, board); answer = min(res, answer); return; } CCTV& ctv = cctvVec[index]; for (int i = 0; i < rotCntVec[ctv._type]; i++) { RotateVec(ctv, i); dfs(index + 1); RotateVec(ctv, i * -1); } } int main() { cin >> N >> M; board.resize(N, vector<int>(M)); for (int i=0; i<N; i++) { for (int j=0; j<M; j++) { int val; cin >> val; board[i][j] = val; if (val == 0) cnt++; if (1 <= val && val <= 5) cctvVec.push_back({i,j,val,rotVecs[val]}); } } dfs(0); cout << answer << '\n'; return 0; }
3. 연구소
1) 문제
문제 설명
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
2) 문제 분석 및 풀이
1) 설계, 분석
2) 풀이
#include <string> #include <vector> #include <climits> #include <algorithm> #include <iostream> #include <queue> using namespace std; struct Cell { int _x; int _y; int _type; }; int N,M; int cnt = 0; int wallCNT = 3; int answer = INT_MIN; vector<vector<int>> board; vector<Cell> virusVec; vector<Cell> emptyVec; int dx[4] = {0,1,0,-1}; int dy[4] = {1,0,-1,0}; bool CanGo(int x, int y, vector<vector<int>>& inboard) { if ( x < 0 || x >= N ) return false; if ( y < 0 || y >= M ) return false; if ( inboard[x][y] != 0) return false; return true; } void runBFS(std::vector<std::vector<int>> boardCopy, int& remainingEmptyCells) { std::queue<Cell> q; // 모든 초기 바이러스 위치에서 BFS 시작 for (const auto& virus : virusVec) { q.push(virus); } while (!q.empty()) { Cell current = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = current._x + dx[i]; int ny = current._y + dy[i]; // 이동할 수 있는 곳이라면 (빈칸 0인 곳) if (CanGo(nx, ny, boardCopy)) { boardCopy[nx][ny] = 2; // 바이러스 감염 remainingEmptyCells--; // 안전 영역 감소 q.push({nx, ny}); } } } } void dfs() { vector<bool> v(emptyVec.size() - wallCNT, false); v.insert(v.end(), wallCNT, true); do { // 빈칸중에서 벽을 세울 3개 뽑기 vector<Cell> currentCombination; for (int i = 0; i < emptyVec.size(); i++) { if (v[i]) currentCombination.push_back(emptyVec[i]); } // 3개 위치에 벽 세우기 for (int i=0; i<3; i++) { int x = currentCombination[i]._x; int y = currentCombination[i]._y; board[x][y] = 1; cnt--; } // 각 바이러스에 대해서 bfs하기 int res = cnt; runBFS(board, res); answer = max(answer, res); // 원상복구 하기 for (int i=0; i<3; i++) { int x = currentCombination[i]._x; int y = currentCombination[i]._y; board[x][y] = 0; cnt++; } } while (next_permutation(v.begin(), v.end())); } int main() { cin >> N >> M; board.resize(N,vector<int>(M)); for (int i=0; i<N;i++) { for (int j=0; j<M; j++) { int val; cin >> val; board[i][j] = val; if (val == 2) virusVec.push_back({i,j,2}); else if (val == 0) { emptyVec.push_back({i,j,0}); cnt++; } } } dfs(); cout << answer << "\n"; return 0; }
