친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다!
갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직아이를 사용해 벼락치기를 하기로 한다.
성민이가 듣는 과목의 교과서는, 알파벳 소문자(a-z)와 알파벳 대문자(A-Z)로만 이루어져 있다. 성민이가 교과서에서 찾고자 하는 키워드도 역시 알파벳 소문자와 대문자로만 이루어져 있다. 하지만, 성민이에겐 큰 문제가 생겼다. 결석한 날의 수업 내용을 친구에게 빌려 필기를 하던 중, 교과서에 숫자(0-9)를 적어버린 것이다.
키워드를 찾기 힘들어 패닉에 빠진 성민이는 몇 안 되는 친구인 당신에게 도움을 요청했다. 성민이를 도와, 교과서에서 성민이가 찾고자 하는 키워드의 존재 여부를 알려주자.
입력
첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 100) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 주어진다. (1 ≤ |K| ≤ 100).
단, 입력으로 들어오는 키워드 문자열 K의 길이는, 교과서의 문자열 S보다 짧거나 같다.
출력
첫 번째 줄에 성민이가 찾고자 하는 키워드가 문자열 내에 존재하면 1, 존재하지 않으면 0을 출력한다.
접근 방법
입력 받은 문자열을 하나씩 따져가면서 해당 문자에서 '0'을 빼서 int 형으로 바꿔본다.
바꾼 수가 0~9 사이이면 패스하고, 아니라면 string removedNum에 해당 문자를 붙인다.
removedStr.find()를 사용해서 부분 문자열의 포함 여부를 알 수 있다.
참고로 포함 되었을 때 find()는 removedStr 중 부분 문자열이 포함된 첫 인덱스를 리턴한다.
가톨릭대학교에 다니는 컴퓨터정보공학부 황톨릭은 코로나 때문에 슬퍼하는 친구들을 위해 게임을 하나 만들었다.
게임이 시작되면 알파벳 대문자로만 이루어진 문자열이 주어진다. 문자열이 주어지면 각 문자의 획수로 문자를 변환한다. 획수들을 갖고 앞에서부터 두 개씩 더해가는데 만약 짝이 지어지지 않는다면 그대로 다음 단계로 내려간다. 다음 단계부터는 이전 단계에서 두 개씩 더해가며 생성된 숫자들을 가지고 같은 과정을 반복한다. 과정을 반복하다가 결국 마지막 한 개의 수가 남았을 때 그 수가 홀수라면 이기는 것이고 짝수라면 지는 게임이다!!
예를 들어 "ABCDE"라는 문자열이 주어지면 ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ 각 문자의 획수인 3, 2, 1, 2, 3으로 바꾸어 아래의 그림처럼 과정을 진행한다. 단, 계산할 때, 더한 값이 10을 넘는다면 10으로 나눈 나머지로 바꿔준다.
‘E’의 경우는 짝을 지을 수 없으므로 3이 바로 내려오게 된다. 결국, 마지막 남은 수가 1인 홀수이므로 이 게임은 이기게 되는 것이다.
게임의 심판역할인 톨릭이는 매번 계산하는 게 귀찮아 코드를 짜놓고 싶어한다. 톨릭이를 도와 코드를 짜주자!!
알파벳 대문자의 획수는 아래 표와 같다.
접근 방법
계산의 편의를 위해서 int, string, char를 적절하게 변환해야 하는 문제였다.
char -> int : char에 '0'을 빼주면된다. int or char -> string : to_string()를 쓰면 된다.
알고리즘은 아래 단계와 같다.
1) 획수를 alpha[] 에 차례로 저장한다.
2) 입력 문자열에 대한 획수를 alpha[]에서 구한 다음, 그 획수를 string 형으로 바꿔서 쭉 붙이고 cntStr에 저장한다. 즉, 입력문자열이 "ABCDE" 면 cntStr는 "32123"이 저장된다.
3) cntStr의 길이가 1이 될 때까지 while문을 반복한다.
3)-1. 획수가 쭉 이어져 있는 문자열인 cntStr를 따라가면서 짝지어서 획수를 더해서 계산한다.
3)-2. 그 계산 값을 문자열 tmp에 'push_back()함수' 또는 '+=' 연산을 이용해서 붙여준다.
3)-3. 짝이 안 맞는 수가 하나 남으면 마지막에 tmp에 그대로 이어 붙여준다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
int alpha[26] = {3,2,1,2,3,3,3,3,1,1,3,1,3,3,1,2,2,2,1,2,1,1,2,2,2,1};
int main(){
string str; cin >> str;
string cntStr = "";
for(int i = 0; i<str.length(); i++){
cntStr += to_string(alpha[str[i]-65]);
}
while(cntStr.length()>1){
int len = cntStr.length();
if(len == 1) break;
string tmp = "";
if(len % 2 != 0)
{ //짝 안 맞는게 하나 있을 때
for(int i = 0; i<len-1; i+=2){
int num = ((cntStr[i]-'0') + (cntStr[i+1]-'0'))%10;
tmp += to_string(num);
}
tmp.push_back(cntStr[len-1]);
cntStr = tmp;
}
else
{ //모두 짝이 맞을 때
for(int i = 0; i<len; i+=2){
int num = ((cntStr[i] - '0') + (cntStr[i + 1] - '0')) % 10;
tmp += to_string(num);
}
cntStr = tmp;
}
}
int res = cntStr[0] - '0';
if(res % 2 != 0) {
cout << "I'm a winner!";
}
else{
cout << "You're the winner?";
}
return 0;
}
아직 글을 모르는 영석이가 벽에 걸린 칠판에 자석이 붙어있는 글자들을 붙이는 장난감을 가지고 놀고 있다.
이 장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다. 영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다.
A A B C D D a f z z 0 9 1 2 1 a 8 E W g 6 P 5 h 3 k x
<그림 1>
한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 다섯 개의 단어들의 글자 개수는 서로 다를 수 있다.
심심해진 영석이는 칠판에 만들어진 다섯 개의 단어를 세로로 읽으려 한다. 세로로 읽을 때, 각 단어의 첫 번째 글자들을 위에서 아래로 세로로 읽는다. 다음에 두 번째 글자들을 세로로 읽는다. 이런 식으로 왼쪽에서 오른쪽으로 한 자리씩 이동 하면서 동일한 자리의 글자들을 세로로 읽어 나간다. 위의 그림 1의 다섯 번째 자리를 보면 두 번째 줄의 다섯 번째 자리의 글자는 없다. 이런 경우처럼 세로로 읽을 때 해당 자리의 글자가 없으면, 읽지 않고 그 다음 글자를 계속 읽는다. 그림 1의 다섯 번째 자리를 세로로 읽으면 D1gk로 읽는다.
그림 1에서 영석이가 세로로 읽은 순서대로 글자들을 공백 없이 출력하면 다음과 같다:
Aa0aPAf985Bz1EhCz2W3D1gkD6x
칠판에 붙여진 단어들이 주어질 때, 영석이가 세로로 읽은 순서대로 글자들을 출력하는 프로그램을 작성하시오.
입력
총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’ 중 하나이다. 각 줄의 시작과 마지막에 빈칸은 없다.
출력
영석이가 세로로 읽은 순서대로 글자들을 출력한다. 이때, 글자들을 공백 없이 연속해서 출력한다.
접근 방법
브론즈 1단계 문제로 간단하게 해결할 수 있다.
배열 크기의 최대값인 [5][15]만큼 '.'로 초기화 한뒤, 5개의 문자열을 입력받는다.
입력을 다 한 후 세로로 읽다가 '.'이 나오면 해당 칸은 글자가 없는 것을 의미하므로 continue로 건너 뛰고 다음 행의 문자를 탐색한다.
'.'가 아니면 push_back() 를 이용하여 정답 문자열에 해당 문자를 추가한다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
char arr[5][15];
int main(){
string str = "";
string answer = "";
for (int r = 0; r < 5; r++)
{
for (int c = 0; c < 15; c++)
{
arr[r][c] = '.';
}
}
for(int i = 0; i<5; i++){
cin >> str;
for(int j = 0; j<str.length(); j++){
arr[i][j] = str[j];
}
}
for(int c = 0; c<15; c++){
for (int r = 0; r < 5; r++)
{
if (arr[r][c] == '.') continue;
answer.push_back(arr[r][c]);
}
}
cout << answer;
return 0;
}
암호학에서 치환 암호(substitution cipher)란, 평문에 들어있는 각각의 문자를 주어진 치환 방법으로 암호화하는 방법 중 하나다.
가장 단순한 방법은 평문의 알파벳을 암호문의 알파벳으로 대치시켜 치환시키는 것이다.
예를 들어, 아래와 같은 알파벳 대치표가 주어졌다고 하자.
평문 알파벳 대치표 : abcdefghijklmnopqrstuvwxyz
암호문 알파벳 대치표 : wghuvijxpqrstacdebfklmnoyz
위에 주어진 치환 방법을 통해 암호화하면 평문 "hello there"은 "xvssc kxvbv"가 된다.
한 가지 흥미로운 점은 영어 문법 특성상, 알파벳 'e'가 다른 영문 알파벳에 비해 자주 쓰인다는 것이다.
즉, 암호문 알파벳 대치표 없이 암호문을 복호화하려 할 때, 암호문 알파벳 빈도수를 체크하면 암호문 알파벳 빈도수 중 가장 빈번하게 나타나는 알파벳이 'e'라는 사실을 유추해볼 수 있다.
위 방법으로 암호문 알파벳의 빈도수를 체크하고, 가장 빈번하게 나타나는 문자를 출력하는 프로그램을 작성하면 된다.
만약 주어진 암호문에서 가장 빈번하게 나타나는 문자가 여러 개일 경우, 그 빈번한 문자 중 어느 것이 평문 알파벳 'e'를 가리키는지 확실하게 알 수 없기 때문에 "모르겠음"을 의미하는 '?'를 출력하면 된다.
입력
입력의 T(1 ≤ T ≤ 20)는 테스트 케이스로, 입력 제일 상단에 주어진다. 각각의 테스트 케이스는 한 줄마다 소문자와 공백으로 이루어진 영어 문장이 주어진다. 이 문장의 길이는 적어도 1이상이며 255이하다.
출력
각각의 테스트 케이스에 대해, 가장 빈번하게 나타나는 문자를 출력하거나 빈번하게 나타나는 문자가 여러 개일 경우 '?'를 출력한다.
접근 방법
주의할 점 : getline(cin, str)으로 공백 포함한 한 줄을 받기 전에, cin>>T 이후의 입력 버퍼를 비우도록 하자!! 입력 버퍼 비우지 않으면 입력한 값을 T에 저장하고 남은 '\n'가 밀려서 그 다음의 getline(cin, str)의 str로 들어가게 돼서 입력값이 하나씩 밀리는 문제가 발생한다. 자세한 내용은 아래의 링크를 참고하자.
서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 주인 자리에서 쫓겨난지 오래이다. 그나마 다행인 것은 AI가 인간을 적대적으로 대하지 않고, 도리어 AI가 쌓아올린 눈부신 기술의 발전으로 모든 사람이 무제한적인 재화를 사용할 수 있게 되어 한 세기 전의 사람들이 바라던 돈 많은 백수와 같은 삶을 누릴 수 있게 됐다는 사실이다. 대다수의 인간들은 현재의 상황에 만족하고 더 이상 발전을 포기한 채 놀고 먹으면서 시간을 보내고 있지만 일부 인간들은 인류의 영광을 되찾기 위해 저항군을 조직해 AI에게 투쟁하고 있다.
저항군은 AI에게 승산이 있는 종목을 찾고 있다. 이러한 종목을 가지고 AI에게 승부를 걸어 전 인류에게 도전정신과 인간의 위대함을 증명하고 싶기 때문이다. 저항군의 지도부는 무려 12시간에 걸쳐 AI에게 승산이 있는 종목을 찾기 위한 회의를 진행했다. 회의에서 알고리즘 문제 풀이 대결, 가위불바위총번개악마용물공기보스펀지늑대나무사람뱀 게임, 캐치마인드, 알까기, 스타크래프트, 똥 피하기 게임, 딸기 2비트, 딸기수박당근참외메론 게임, 백일장, 사생 대회 등 다양한 아이디어가 나왔지만 단 0.01%라도 승산이 있어 보이는 종목은 하나도 없었다.
그렇게 모두가 낙담하던 중 누군가가 역사책을 뒤져 인간이 AI에게 승산이 있는 종목을 찾아냈다. 바로 정확히 100년 전에 있었던 이세돌과 알파고의 바둑 대결이었다. 물론 알파고는 그 이후로 발전을 거듭했기에 바둑에서의 승산은 없지만 바둑의 룰을 변형한 Baduk2라는 종목에서는 이세돌이 알파고에게 한 세트를 이긴 것과 같이 인간이 AI에게 승산이 있다고 판단했다.
Baduk2의 룰은 바둑과 거의 유사하지만 양 선수가 돌을 1개씩 번갈아 두는 것이 아니라 2개씩 둔다는 점이 다르다. 서술의 편의를 위해 상하좌우로 인접한 같은 색 돌의 집합을 그룹이라고 하자. 아래의 판에서는 흑의 그룹과 백의 그룹이 각각 3개씩 존재한다.
Baduk2에서는 일반적인 바둑과 동일하게 자신의 돌로 상대방의 그룹을 빈틈없이 에워싸면 갇힌 돌을 죽일 수 있다. 어느 그룹이 빈틈없이 에워싸였다는 것은 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것과 동치이다.
그리고 Baduk2에서는 모든 비어있는 칸에 돌을 둘 수 있다. 설령 상대 돌로 둘러싸여 있어 스스로 잡히는 곳이라고 하더라도 상관이 없다. 아래와 같은 상황을 생각해보자.
두 빨간 칸 모두 백의 입장에서 착수할 경우 연결된 그룹이 흑돌로 둘러싸이게 되어 원래 바둑의 규칙에서는 백의 입장에서 스스로 잡히는 곳이지만 Baduk2에서는 이와 무관하게 백이 빨간 칸 두 곳에 착수해 8개의 흑돌이 들어있는 그룹의 돌을 죽일 수 있다.
저항군은 AI에게 Baduk2로 도전장을 내밀었고 AI는 의외로 순순히 도전을 받아들였다. 이제 저항군은 2116년 3월 9일, 인류의 자존심을 건 Baduk2 대결을 시작한다. 그리고 당신에게 인류의 승리를 돕기 위해 현재 판 위에서 돌 2개를 두어 상대 돌을 최대한 많이 죽이게끔 하는 프로그램을 작성하는 임무가 주어졌다. 인류의 명예를 걸고 현재 판이 주어질 때 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 구하는 프로그램을 작성하자.
입력
첫째 줄에 바둑판의 행의 갯수와 열의 갯수를 나타내는 N(3 ≤ N ≤ 20)과 M(3 ≤ M ≤ 20)이 한 칸의 빈칸을 사이에 두고 주어진다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 빈 칸, 1은 나의 돌, 2는 상대의 돌을 의미한다. 빈 칸이 2개 이상 존재함과 현재 바둑판에서 양 플레이어 모두 상대방의 돌로 빈틈없이 에워싸인 그룹이 없음이 모두 보장된다.
출력
첫째 줄에 현재 판에서 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 출력한다.
접근 방법
DFS와 두번의 BFS를 활용하면 쉽게 풀 수 있는 문제였다.
알고리즘은 크게 아래의 두 단계로 나뉜다.
1) 빈 칸들 중에서 "내 돌 두개를 놓을 좌표 두개" 를 고르는 모든 경우를 구한다. (DFS)
2) 내 돌 두개를 놓았으면, 그 상태에서 내 돌에 둘러쌓여 죽는 상대 돌의 개수를 구한다. -> 이 개수를 비교해서 최대 값을 구한다.
그럼 2)에서 죽게되는 상대 돌의 개수를 어떻게 구할까?
먼저, BFS를 이용해서 상대 돌의 그룹들을 구한다. 각 그룹의 시작 좌표를 "partnerGroup_StartLoc" 벡터에 저장한다.
그 후, 이 벡터에 저장된 [상대 돌 그룹의 시작 좌표] 에서 한번 더 BFS를 돌린다. BFS는 아래와 같이 동작한다.
//어느 그룹이 빈틈없이 에워싸였다는 것 <=> 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것
int getKilled(){
int ret = 0;
int v[20][20];
for (int i = 0; i < partnerGroup_StartLoc.size(); i++)
{ //BFS로 흰색 그룹들 모두 검사. 둘러 쌓여있는 그룹에서 죽는 돌 개수 세기
queue<pair<int,int>> tmpQue;
memset(v, 0, sizeof(v));
int r = partnerGroup_StartLoc[i].first;
int c = partnerGroup_StartLoc[i].second;
v[r][c] = 1;
int killedCnt = 1;
bool isContinue = true;
tmpQue.push(make_pair(r,c));
while(!tmpQue.empty()){
int cr = tmpQue.front().first;
int cc = tmpQue.front().second;
tmpQue.pop();
for (int k = 0; k < 4; k++)
{
int nr = cr + dr[k];
int nc = cc + dc[k];
if (nr < 0 || nr >= N || nc < 0 || nc >= M || v[nr][nc]==1) continue;
//빈칸이랑 인접했으면 그 그룹은 에워쌓이지 않은 것.
if(map[nr][nc] == 0){
isContinue = false;
break;
}
//백돌끼리 인접한 것이므로 큐에 담고 계속해서 검사 진행한다.
if(map[nr][nc] == 2){
v[nr][nc] = 1;
killedCnt++;
tmpQue.push(make_pair(nr,nc));
}
}
if(!isContinue) break;
}
if(isContinue){ //모두 둘러 쌓인 경우에만 합해준다.
ret += killedCnt;
}
}
return ret;
}
- next좌표가 2이면 v[][]에 방문했음을 표시한다.
- next좌표가 0이면 빈칸이므로 해당 그룹은 내 돌에 의해 둘러 쌓여있지 않은 그룹이므로 패스하고 다음 그룹을 검사한다.
- next좌표가 1이면 큐에 담지 않고 계속해서 큐에 담긴 좌표들 검사를 진행한다.
그 그룹이 모두 빈칸이랑 한번도 인접한 적이 없다면 죽은 돌의 개수를 합한다.
모든 그룹을 검사해서 죽은돌의 개수 합을 리턴하며, 리턴된 값들 중 최대값을 구해서 출력하면 된다..
전체 코드는 아래와 같다.
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <string.h>
using namespace std;
int map[20][20];
int visited[20][20];
int N, M;
//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int answer = 0;
vector<pair<int,int>> spaceVec;
vector<pair<int, int>> partnerGroup_StartLoc;
vector<int> pickedIdxVec;
int picked[400] = {0,};
//상대편 돌들의 그룹 표시하기 위한 함수
void BFS(int r, int c){
visited[r][c] = 1;
queue<pair<int,int>> que;
que.push(make_pair(r,c));
while(!que.empty()){
int cr = que.front().first;
int cc = que.front().second;
que.pop();
for(int i = 0; i<4; i++){
int nr = cr + dr[i];
int nc = cc + dc[i];
if(nr<0 || nr>=N || nc<0 || nc>=M || visited[nr][nc] == 1 || map[nr][nc] != 2) continue;
visited[nr][nc] = 1;
que.push(make_pair(nr, nc));
}
}
}
//어느 그룹이 빈틈없이 에워싸였다는 것 <=> 그 그룹 내에 빈 칸과 인접해있는 돌이 하나도 없다는 것
int getKilled(){
int ret = 0;
int v[20][20];
for (int i = 0; i < partnerGroup_StartLoc.size(); i++)
{ //BFS로 흰색 그룹들 모두 검사. 둘러 쌓여있는 그룹에서 죽는 돌 개수 세기
queue<pair<int,int>> tmpQue;
memset(v, 0, sizeof(v));
int r = partnerGroup_StartLoc[i].first;
int c = partnerGroup_StartLoc[i].second;
v[r][c] = 1;
int killedCnt = 1;
bool isContinue = true;
tmpQue.push(make_pair(r,c));
while(!tmpQue.empty()){
int cr = tmpQue.front().first;
int cc = tmpQue.front().second;
tmpQue.pop();
for (int k = 0; k < 4; k++)
{
int nr = cr + dr[k];
int nc = cc + dc[k];
if (nr < 0 || nr >= N || nc < 0 || nc >= M || v[nr][nc]==1) continue;
//빈칸이랑 인접했으면 그 그룹은 에워쌓이지 않은 것.
if(map[nr][nc] == 0){
isContinue = false;
break;
}
//백돌끼리 인접한 것이므로 큐에 담고 계속해서 검사 진행한다.
if(map[nr][nc] == 2){
v[nr][nc] = 1;
killedCnt++;
tmpQue.push(make_pair(nr,nc));
}
}
if(!isContinue) break;
}
if(isContinue){ //모두 둘러 쌓인 경우에만 합해준다.
ret += killedCnt;
}
}
return ret;
}
void pickDFS(int toPick){
if(toPick==0)
{ //돌 놓을 위치 2개 골랐으면, 그 상태에서 죽일 수 있는 상대 돌의 최대 갯수 구하기
int r1 = spaceVec[pickedIdxVec[0]].first;
int c1 = spaceVec[pickedIdxVec[0]].second;
int r2 = spaceVec[pickedIdxVec[1]].first;
int c2 = spaceVec[pickedIdxVec[1]].second;
map[r1][c1] = 1; map[r2][c2] = 1; //내 돌 놓기
int sum = getKilled();
answer = max(answer, sum);
map[r1][c1] = 0; map[r2][c2] = 0; //원상 복구
return;
}
for(int i = 0; i<spaceVec.size(); i++){
if(picked[i] == 0){
picked[i] = 1;
pickedIdxVec.push_back(i);
pickDFS(toPick-1);
pickedIdxVec.pop_back();
picked[i] = 0;
}
}
}
int main()
{
cin >> N >> M;
for(int i = 0; i<N; i++){
for(int j = 0; j<M; j++){
cin >> map[i][j];
if(map[i][j] == 0) spaceVec.push_back(make_pair(i,j));
}
}
//상대편 그룹의 시작 위치 찾기
memset(visited, 0, sizeof(visited));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if(map[i][j] == 2 && visited[i][j] == 0){
partnerGroup_StartLoc.push_back(make_pair(i,j));
BFS(i,j);
}
}
}
//빈공간에서 내 돌 놓을 곳 2개 고르기 -> 완전탐색
pickDFS(2);
cout << answer;
return 0;
}
십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 0보다 크거나 같아야 한다.
아래 그림은 크기가 0, 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.
십자가의 넓이는 포함된 '*'의 개수이다. 크기가 0, 1, 2, 3인 십자가의 넓이는 1, 5, 9, 13이다.
크기가 N×M이고, '.'과 '#'로 이루어진 격자판이 주어진다. 격자판에 두 개의 십자가를 겹치지 않게 놓으려고 한다. 십자가는 '#'가 있는 칸에만 놓을 수 있다. 놓인 십자가 넓이의 곱의 최댓값을 구해보자.
입력
첫째 줄에 격자판의 크기 N, M (2 ≤ N, M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다. 항상 두 개의 십자가를 놓을 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 놓은 십자가 넓이의 곱의 최댓값을 출력한다.
접근 방법
첫번째 십자가의 가능한 크기가 0부터 max라고 했을 때,
모든 경우에 대해, 두번째 십자가의 가능한 크기를 모두 구해서 최대 넓이를 구하는 방식이다.
처음에는,
십자가 중심 2개를 (r1, c1), (r2, c2) 라고 했을 때, DFS를 이용하여 모든 (r1, c1), (r2, c2) 의 조합을 구했다.
그 후, 십자가 두개의 크기를 각각 1씩 증가시켜 나가면서 넓이를 구했다.
그러나 이 방식은 완전탐색이 아니다.
왜냐하면 1번 십자가의 크기를 1 증가시킨 후 -> 1번과 2번 십자가가 겹치지 않는 한에서 2번 십자가의 크기를 1 증가한 뒤 넓이를 계산했기 때문이다. 완전탐색을 하려면 반대 순으로도 넓이를 각 경우에 대해 계산해야하며, 중간에도 계산을 한번 더 해야한다.
즉, 아래와 같이 여러번의 계산이 필요한 것이다.
1번 십자가 크기 1 증가 -> 넓이 계산 -> 2번 십자가 크기 1 증가 -> 넓이 계산 2번 십자가 크기 1 증가 -> 넓이 계산 -> 1번 십자가 크기 1 증가 -> 넓이 계산
또한, 아래 링크의 테스트케이스는 4달 전에 추가된 데이터로, 이 경우도 주의해야한다.
이렇게 두가지 고려할 점이 있지만
첫번째 십자가의 가능한 크기가 0부터 max라고 했을 때, 모든 경우에 대해, 두번째 십자가의 가능한 크기를 모두 구해서 최대 넓이를 구하는 방식이다.
이 방식으로 그냥 모든 가능한 경우를 완전탐색하면 보다 단순하게 해결 가능하다.
#include <iostream>
#include <vector>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;
int N, M;
char map[15][15];
int answer = 0;
//위 오 아 왼
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
//(r,c)가 중심일 때, 가능한 십자가의 최대 크기
int getSize(int r, int c){
int ret = 0;
while(1){
bool flag = true;
for(int i = 0; i<4; i++){
int nr = r + dr[i]*ret;
int nc = c + dc[i]*ret;
if(nr<0 || nc<0 || nr>=N || nc>=M || map[nr][nc] != '#'){
flag = false;
break;
}
}
if(flag) ret++;
else break;
}
return ret - 1; //ret가 0부터 시작하므로, 처음 통과하면 ret=1이 되는데 이때 십자가의 크기는 0임 ('*' 한개짜리)
}
//중심이 (r,c)이고 크기가 K인 십자가를 만들거나(val='#') 십자가 원상복구(val='.')
void make_cross(int r, int c, int k, int val){
for(int i = 0; i<=k; i++){
for(int j = 0; j<4; j++){
int nr = r + dr[j]*i;
int nc = c + dc[j]*i;
map[nr][nc] = val;
}
}
}
int main()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> map[i][j];
}
}
for(int i = 0; i<N; i++){
for(int j = 0; j<M; j++){
if(map[i][j] == '#'){
int step1 = getSize(i,j);
for (int k = 0; k <= step1; k++) //첫번째 십자가 크기 1부터 max까지,
{
make_cross(i,j,k,'*'); //첫번째 십자가 표시
for(int r = 0; r<N; r++){
for(int c=0; c<M; c++){
if(map[r][c] == '#'){
int step2 = getSize(r,c); //각 크기에 대해 두번째 십자가 크기 구하기
int width1 = 4*k + 1;
int width2 = 4*step2 + 1;
answer = max(answer, width1*width2);
}
}
}
make_cross(i,j, k, '#'); //첫번째 십자가 원상복구
}
}
}
}
cout << answer;
return 0;
}
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.
오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.
파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.
파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.
파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.
아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.
가로
세로
대각선
가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.
입력
첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.
출력
첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.
접근 방법
DFS를 활용한 재귀로 완전탐색을 해 준다.
dr[], dc[]에 가로, 세로, 대각선 방향의 수를 저장하고 for()문에서 가로,세로,대각선을 반복하면서 파이프의 끝 위치를 옮긴다.
이때, 가능한 조합 중, "가로->세로 "와 "세로->가로"는 이동할 수 없는 조합이므로, 이를 제외한다.
또한 주의할 점은 대각선일 때이다.
아래의 그림처럼 파이프의 끝이 (2,3) -> (3,4)로 이동하는 경우에, (3,4)뿐만 아니라 (2,4)와 (3,3)도 모두 벽이 아니어야 이동할 수 있기 때문에 이 두개 중 벽이 하나라도 있는 경우는 제외한다.
