정보/백준 문제풀이
백준 30928번 Yokohama Phenomena C++
FeatherCoder
2024. 3. 23. 16:50
문제 링크 : https://www.acmicpc.net/problem/30928
30928번: Yokohama Phenomena
Do you know about Yokohama Phenomena? The phenomenon takes place when three programmers, sitting around a table, hold a single pen together above a board. A grid of squares is drawn on the board, with each square marked with a single letter. Although none
www.acmicpc.net
백준에서 대회 문제들을 찾아보다가 이 문제를 발견했는데 실버1이기도 하고, 재미있게 생겨서 시도해보았다.
문제 풀이
문제는 m x n 격자칸에 알파벳들이 적혀있을 때 인접한 칸끼리 이어서 만들 수 있는 YOKOHAMA의 개수를 묻고 있다. m과 n이 모두 10 이하여서 알파벳이 최대 100개까지 밖에 없다. 이런 문제는 노가다로 풀어도 괜찮아보인다. DFS로 Y부터 출발해 가능한 모든 경우를 탐색해보자.
1. 입력
입력 부분에서는 m과 n을 입력 받고, table 배열에 m x n격자판을 저장하자. 또, vector에 pair형태로 Y의 모든 좌표들을 저장해주자.
char table[11][11]; //격자판
int main()
{
int n,m;
cin>>n>>m;
vector<pair<int,int>> Y_location(100);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>table[i][j];
if(table[i][j]=='Y')
{
Y_location.push_back(make_pair(i,j));
}
}
}
}
이제 해야할 것은 각각의 Y의 좌표에 대해서 가능한 모든 방법의 경우의 수를 구하고, 합치는 것이다.
int S = 0; //총 가짓수
for(int i=0;i<Y_location.size();i++)
{
S += dfs(Y_location[i],"Y");
}
cout<<S;
2. 경우의 수 구하기
문자열 "YOKOHAMA"에서 Y다음에 O가 오고, O다음에 K, K다음에 O, .... , M다음에 A가 온다. 따라서 각각의 문자에 대해서 그 다음에 오는 '인접한' 문자를 queue에 담아주는 식으로 탐색해주자. 마지막 A에 대해서는 문자열에 끝이므로 카운터에 1을 추가해주면 된다.
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
char table[11][11];
queue<pair<pair<int,int>,string>> q;
int dfs(pair<int,int> c, string s)
{
int k = 0; //가능한 개수
q.push(make_pair(c,s)); //c:문자의 좌표 s:문자(ex>'Y','A')
while(!q.empty())
{
pair<int,int> coord = q.front().first;
string s1 = q.front().second;
q.pop();
if(s1=="Y")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='O')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"O1"));
}
}
}
else if(s1=="O1")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='K')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"K"));
}
}
}
else if(s1=="K")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='O')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"O2"));
}
}
}
else if(s1=="O2")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='H')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"H"));
}
}
}
else if(s1=="H")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='A')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"A1"));
}
}
}
else if(s1=="A1")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='M')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"M"));
}
}
}
else if(s1=="M")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='A')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"A"));
}
}
}
else if(s1=="A")
{
k++;
}
}
return k;
}코드가 좀 길고 복잡해보일 수 있지만, 같은 패턴을 반복한 것뿐이다. 문제 유형에는 DP가 나와있던데 DP로 푸는 방법은 잘 모르겠다.
코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};
char table[11][11];
queue<pair<pair<int,int>,string>> q;
int dfs(pair<int,int> c, string s)
{
int k = 0;
q.push(make_pair(c,s));
while(!q.empty())
{
pair<int,int> coord = q.front().first;
string s1 = q.front().second;
q.pop();
if(s1=="Y")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='O')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"O1"));
}
}
}
else if(s1=="O1")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='K')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"K"));
}
}
}
else if(s1=="K")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='O')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"O2"));
}
}
}
else if(s1=="O2")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='H')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"H"));
}
}
}
else if(s1=="H")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='A')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"A1"));
}
}
}
else if(s1=="A1")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='M')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"M"));
}
}
}
else if(s1=="M")
{
for(int i=0;i<4;i++)
{
if(table[coord.first+dx[i]][coord.second+dy[i]]=='A')
{
q.push(make_pair(make_pair(coord.first+dx[i],coord.second+dy[i]),"A"));
}
}
}
else if(s1=="A")
{
k++;
}
}
return k;
}
int main()
{
int n,m,S=0;
cin>>n>>m;
vector<pair<int,int>> Y_location(100);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>table[i][j];
if(table[i][j]=='Y')
{
Y_location.push_back(make_pair(i,j));
}
}
}
for(int i=0;i<Y_location.size();i++)
{
S += dfs(Y_location[i],"Y");
}
cout<<S;
}