[boj][c++] 10026 적록색약, 1021 회전하는 큐

ppparkta·2022년 8월 4일

Problem solving

목록 보기

23/65

10026 적록색약

bfs로 풀었다. 실버 문제로 연습하고 접근하니까 골드 문제도 스스로 풀 수 있게 됐다. 뿌듯. 그래도 좌표 쓰는 문제는 여전히 어렵다ㅜ

로직은 적록색약인 방문기록과 비적록색약인 방문기록을 나눠서 관리하는 것이다. bfs_rgb()와 bfs_rb()를 함수로 나눴다.

#include    <iostream>
#include    <queue>
using namespace std;

int n, rb, rgb;
char graph[101][101];
int visit_rb[101][101];
int visit_rgb[101][101];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void bfs_rb(int x, int y)
{
    queue<pair<int,int>>q;
    char cmp=graph[x][y];
    q.push({x,y});
    visit_rb[x][y]=1;
    while(!q.empty())
    {
        int nx=q.front().first;
        int ny=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int xx=nx+dx[i];
            int yy=ny+dy[i];
            char ncmp=graph[xx][yy];
            if((xx>=0&&xx<n)&&(yy>=0&&yy<n))//가능한 범위 내
            {
                if(visit_rb[xx][yy]==0)//방문한 적 없고 같은 구역
                {
                    if(((cmp=='R'||cmp=='G')&&(ncmp=='R'||ncmp=='G'))||cmp==ncmp)
                    {   
                        q.push({xx,yy});
                        visit_rb[xx][yy]=1;
                    }
                }
            }
        }
    }
}

void bfs_rgb(int x, int y)
{
    queue<pair<int,int>>q;
    q.push({x,y});
    visit_rgb[x][y]=1;
    while(!q.empty())
    {
        int nx=q.front().first;
        int ny=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int xx=nx+dx[i];
            int yy=ny+dy[i];
            if((xx>=0&&xx<n)&&(yy>=0&&yy<n))//가능한 범위 내
            {
                if(visit_rgb[xx][yy]==0)//방문한 적 없고 같은 구역
                {
                    if(graph[x][y]==graph[xx][yy])
                    {   
                        q.push({xx,yy});
                        visit_rgb[xx][yy]=1;
                    }
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>graph[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(visit_rb[i][j]==0)
            {
                rb++;
                bfs_rb(i,j);
            }
            if(visit_rgb[i][j]==0)
            {
                rgb++;
                bfs_rgb(i,j);
            }
        }
    }
    cout<<rgb<<" "<<rb<<endl;
}

1021 회전하는 큐

제목만 보면 단순 큐를 이용해 풀수있을 것 같지만 조건이 몇개 붙어있기 때문에 deque을 사용해서 풀었다. 연산은 총 세개인데

pop_front()
push_back(front()), pop_front()
push_front(back()), pop_back()

이렇게 묶음으로 세개다. 이 중 우리가 카운트해야 하는 것은 2와 3 연산으로, 사실상 자료를 pop하는건 1번 연산이 유일하고 2와 3은 자료를 앞에서 뒤로, 뒤에서 앞으로 이동하는 것에 불과하다.

몇번의 연산을 통해 자료의 인덱스가 계속해서 바뀌기 때문에, 단순히 원하는 값을 바로 연산에 이용하는 것이 아닌, 인덱스를 구해서 연산하려는 접근이 필요하다.

#include    <iostream>
#include    <deque>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    static int n,m,cnt;
    
    cin>>n>>m;
    deque<int> d;
    for(int i=1;i<=n;i++)
    {
        d.push_back(i);
    }
    for(int i=0;i<m;i++)
    {
        int a, idx;
        cin>>a;
        for(int j=0;j<d.size();j++)
        {
            if(d[j]==a)
            {
                idx=j;
                break;
            }
        }
        if(idx<d.size()-idx)
        {
            while(true)
            {
                if(a==d.front())
                {
                    d.pop_front();
                    break;
                }
                else
                {
                    cnt++;
                    d.push_back(d.front());
                    d.pop_front();
                }
            }   
        }
        else
        {
            while(true)
            {
                if(a==d.front())
                {
                    d.pop_front();
                    break;
                }
                else
                {
                    cnt++;
                    d.push_front(d.back());
                    d.pop_back();
                }
            }
        }
    }
    cout<<cnt<<endl;
}