BFS 썸네일형 리스트형 [python] baekjoon 2549 : 루빅의 사각형 문제 -> 문제 링크 : https://www.acmicpc.net/problem/2549 2549번: 루빅의 사각형 첫 번째 줄에는 움직이는 횟수를, 두 번째 줄부터는 한 줄에 하나씩 타일을 움직이는 방법을 순서대로 출력한다. 이때, 격자판의 i번째 행을 k칸 움직였다면 정수 1과 i와 k를 빈칸을 사이에 두고 www.acmicpc.net 문제풀이 입력값은 2차원 배열이지만 1차원 배열로 만들어 16자리의 수열을 정렬시키는 문제로 풀면 된다. 이때 숫자를 배열보다는 문자열로 만드는 게 딕셔너리를 사용할 때 시간이 적게 든다. 하지만 10을 넘는 숫자가 있어 2차원 배열에서의 자리를 유추하기가 힘들다. 모든 숫자가 한 글자가 되도록 16진수의 수로 바꿔 표현하면 1차원 배열의 자리를 보고 2차원 배열을 .. 더보기 [python] algospot SORTGAME 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/SORTGAME algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com 문제풀이 문제에서 입력값으로 들어오는 최대 수열의 길이가 8이다. 이떄 만들어질 수 있는 모든 경우의 수는 8! = 4만이다. 가능한 경우의 수가 작기 떄문에 BFS를 통해 문제를 해결할 수 있다. (시간복잡도는?) 모든 가능한 수열을 정점으로 하고 뒤집는 연산을 통해 만들어질 수 있는 수열들은 간선으로 이어 그래프를 만들.. 더보기 이전 1 다음