함수 vs Queue

  • TurtleShip
    TurtleShip

    오늘 Graphical Editor 라는 문제를 풀다가,, 의문점이 생겨서 올립니다.

    똑같은 알고리즘을 하나는 함수를 이용해서 풀었고 하나는 Queue를 이용해서(Breadth First Search) 풀었는데요, 함수를 이용한 것은 통과하는데 Queue를 이용한 것은 Time Limit Excceed가 걸리더군요.

    함수를 이용해서 푼 코드

    [Queue를 이용해서 푼 코드])(http://www.programming-challenges.com/pg.php?page=viewsubmission&subid=450695)

    중요한 부분만 비교하면 첫번째 코드는 Recursion을 이용했구요

    int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,1,-1};
void fillRec(int r, int c, char ori, char change)
{
    pic[r][c] = change;
    for(int i=0; i < 4; i++)
    {
        int nr = r + dr[i];
        int nc = c+ dc[i];
        if(1 <= nr && nr <= R && 1 <= nc && nc <= C && pic[nr][nc] == ori)
            fillRec(nr,nc,ori,change);
    }
}

    int dr[4] = {1,-1,0,0};
int dc[4] = {0,0,1,-1};
queue<int> Q;
Q.push(r);
Q.push(c);

while(!Q.empty())
{
    int cr = Q.front(); Q.pop();
    int cc = Q.front(); Q.pop();
    pic[cr][cc] = color;

    for(int i=0; i < 4; i++)
    {
        int nr = cr + dr[i];
        int nc = cc + dc[i];

        if(1 <= nr && nr <= R && 1 <= nc && nc <= C && pic[nr][nc] == ori)
        {
            Q.push(nr);
            Q.push(nc);
        }
    }
}

    두번째 코드는 queue를 이용했어요.

    제가 Queue로 할 때 뭔가를 잘 못한거 같은데 (함수 : 1초, Queue: 10초 초과), 뭘 틀렸는지를 모르겠어요..

    고수님들 부탁드립니다 ^^


    12년 전
9개의 댓글이 있습니다.
  • VOCList
    VOCList

    두번째 코드에서는 pic[cr][cc] = color; 을 함으로써 방문 표시를 해 주는 시점이 저 위치가 아니라 for문 안의 if 문 안쪽에 push를 할 때 같이 해 줘야 할 것 같습니다. 큐에 한번 넣은 좌표는 그 시점에서 앞으로 방문을 할 것이 예약이 되어 있는 것이고, 방문체크를 미리 해 주지 않으면 같은 좌표가 큐에 여러번 들어갈 수 있기 때문입니다.


    12년 전 link
  • VOCList
    VOCList

    근데 이시간에 안주무시고 뭐하세영...


    12년 전 link
  • TurtleShip
    TurtleShip

    원래 VOCList 님이 말한 방법대로 했었는데 그렇게 하니까 1개의 픽셀만 있는경우 작동을 제대로 하지 않았어요. 생각해보니 원래대로 하면서 while(!Q.empty()) 전에 pic[r][c] = color 를 해주면 되군요 ㅋ


    12년 전 link
  • TurtleShip
    TurtleShip

    아는 동생이랑 술마시고 일어나니까 12시 조금 넘었는데 잠이 안 와서 컴퓨터 하고 있었어요 ㅋ 그러는 님은 안 주무시고 뭐하셨어요 ㅋ;;;


    12년 전 link
  • VOCList
    VOCList

    그러게영..


    12년 전 link
  • Being
    Being

    @VOCList 헐 이분이 몇시에 깨어계신거지


    12년 전 link
  • VOCList
    VOCList

    @Being 알고자의 평화는 내가 지킨다


    12년 전 link
  • Being
    Being

    @VOCList 님 어드민 ㄳㄳ


    12년 전 link
  • VOCList
    VOCList

    @Being 헐 수줍어서 못함 ㅜㅜ


    12년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.