[C++] 백준 1525번: 퍼즐

2023. 7. 4. 19:37·problem solving/백준

🔗문제

1525번: 퍼즐

 

1525번: 퍼즐

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

www.acmicpc.net

 

🖍풀이

한칸이 비워져있는 퍼즐을 순서대로 정렬하기 위한 최소 이동 비용을 구하는 문제

 

빈칸을 기준으로 사방의 셀을 옮겨가며 BFS방식으로 풀 수 있다.

 

 


 

 

🚩 2차원 배열이 아니라 문자열로 표현

 

빈칸을 기준으로 사방의 셀을 이동한다면 당연히 2차원 배열을 생각할 수 있지만, 이 풀이에서는 일련의 문자열로 취급해서 풀어주었다.

 

문자열에서 n 번째에 있는 빈칸을 x, y로 표현하는 법

 

문자열로 된 퍼즐을 BFS에 활용하는 법

최소 이동횟수를 구해야하기 때문에 이미 형성된 퍼즐을 큐에 넣으면 안된다.

map이나 set를 활용하자.

// 전에 탐색했던 퍼즐모양과 같지 않으면 큐에 넣는다
if(visited.find(swabed) == visited.end())
{
    q.push(std::make_pair(swabed, time+1));
    visited.insert(swabed);
}

 

+)

BFS로 풀고 visited의 컨테이너를 세 조합으로 짜봤는데 2가 가장 빨랐다.

  • queue<숫자> + map<숫자> (value)
  • queue<숫자, 이동 횟수> + set<숫자> (bool)
  • queue<숫자> + set<숫자> (이동 횟수는 qSize만큼 while문 돌려 해결)

 

도움된 반례

1 2 3
4 5 0
6 7 8
//정답: 13

🔗 https://www.acmicpc.net/board/view/92488

 

💾 소스

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <set>

const std::string ANSWER = "123456780";
char tmp;

bool isValid(const int r, const int c)
{
    if(r<0 || c<0 || r>=3 || c>=3 )
        return false;

    return true;
}

int BFS(const std::string& initial)
{
    
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    //현재 퍼즐 상태와 이동 횟수
    std::queue<std::pair<std::string, int> > q;
    q.push(std::make_pair(initial, 0));

    // 퍼즐 상태가 문자열로 되어있기 때문에 set을 이용하여 재방문 확인
    std::set<std::string> visited;
    visited.insert(initial);

    std::string puzzle, swaped;
    int time = 0;
    
    while(!q.empty())
    {
        puzzle = q.front().first;
        time = q.front().second;
        q.pop();

        if(puzzle == ANSWER)
        {
            return time;
        }
 
        // 빈칸의 위치를 찾아서 x, y 위치를 파악
        int zero = puzzle.find('0');
        int zx = zero/3;
        int zy = zero%3;

        for(int d=0; d<4; ++d)
        {
            int x = zx + dx[d];
            int y = zy + dy[d];

            if(!isValid(x, y)) continue;

            //swab
            swaped = puzzle;
            tmp = swaped[zero];
            swaped[zero] = swaped[x* 3 + y];
            swaped[x* 3 + y] = tmp;

            // 전에 탐색했던 퍼즐모양과 같지 않으면 큐에 넣는다
            if(visited.find(swaped) == visited.end())
            {
                q.push(std::make_pair(swaped, time+1));
                visited.insert(swaped);
            }
        }
    }
    
    return -1;
}

int main()
{
    std::string puzzle;
    puzzle.resize(9);

    for(int i=0; i<9; ++i)
    {
        std::cin >> tmp;
        puzzle[i] = tmp;
    }
    
    std::cout << BFS(puzzle);

    return 0;
}
저작자표시 비영리 변경금지 (새창열림)
'problem solving/백준' 카테고리의 다른 글
  • [C++] 백준 16137번: 견우와 직녀
  • [C++] 백준 9376번: 탈옥
  • [C++] 백준 17140번: 이차원 배열과 연산
  • [C++] 백준 20056번: 마법사 상어와 파이어볼
u1qns
u1qns
http://github.com/u1qns
  • u1qns
    개발 블로그
    u1qns
  • 전체
    오늘
    어제
    • 분류 전체보기 (173)
      • 회고 (1)
      • programming (17)
        • 개념 정리 (6)
        • CI CD (1)
        • 트러블 슈팅 (0)
        • 환경설정 및 팁 (7)
      • problem solving (155)
        • 개념 정리 (3)
        • 백준 (129)
        • SWEA (15)
        • 프로그래머스 (4)
  • 블로그 메뉴

    • 홈
    • 방명록
  • 링크

    • 깃허브
  • 공지사항

  • 인기 글

  • 태그

    C++
    SSAFY수료식
    구현
    SSAFY
    DP
    백준
    완전탐색
    cmath
    BFS
    POW
    HELLOSSAFY
    cpp
    되추적
    boj
    미해결
    SWEA
    삼성청년SW아카데미
    DFS
    그리디
    투포인터
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
u1qns
[C++] 백준 1525번: 퍼즐
상단으로

티스토리툴바