[책-알고리즘퍼즐68]8.똑똑한 로봇 청소기

문제

 전후 좌우로 움직이는 로봇 청소기가 있다. 또한 같은 장소를 다시 지나다지니 않는다. 이때 이 로봇이 12회 이동할 때, 생각할 수 있는 이동 경로의 패턴이 몇 가지인지 구해 보세요.

 

난이도

IQ 80

 

목표시간

20분

 

풀이(c#,VS)

1.

 

/**
 2020.01.31
 ksj

 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _8_SmartRobotCleaner
{
    class Program
    {
        static int MAXK_COUNT = 12;
        static int[,] dirArr = new int[4,2]{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        static int dd = 0;
        static void Main(string[] args)
        {
            List<int[]> log = new List<int[]>();

            //초기좌표 0,0
            int[] initPos = new int[2]{ 0, 0 };
            log.Add(initPos);

            Console.WriteLine(Move(log));
        }

        static int Move(List<int[]> log)
        {
            if( log.Count == MAXK_COUNT+1)
                return 1;

            int cnt = 0;

            for (int i = 0; i < dirArr.GetLength(0); i++)
            {
                //next move pos
                int[] nextPos = new int[2] { log[log.Count - 1][0] + dirArr[i, 0], log[log.Count - 1][1] + dirArr[i, 1] };

                //can move?
                bool canMove = true;
                for (int j = 0; j < log.Count; j++)
                {
                    if (log[j][0] == nextPos[0] && log[j][1] == nextPos[1])
                    {
                        canMove = false;
                        break;
                    }
                }

                if (canMove)
                {
                    log.Add(nextPos);
                    cnt += Move(log);
                }
            }
            return cnt;
        }
    }
}

 

문제정답(사용언어:python)

1. 깊이 우선 탐색

2. 배열 -1 인덱스는 배열 맨 마지막 인덱스를 뜻함

N = 12

def move(log):

    # 맨 처음 위치를 포함하여 N+1개 조사하면 종료
    if len(log) == N+1:
        return 1

    cnt =0
    #전후 좌우 이동
    for d in [[0,1],[0,-1],[1,0],[-1,0]]:

        # 탐색이 끝나지 않았으면 이동시킴
        next_pos = [log[-1][0] + d[0], log[-1][1] + d[1]]
        print(log, d, next_pos)
        #로그에 다음 위치가 기록되어 있는지 확인하기
        check = False
        for p in log:
            if p[0] == next_pos[0] and p[1] == next_pos[1]:
                check = True # 있는 경우 플래그를  True로 변경
        if check == False:
            cnt += move(log + [next_pos])

    return cnt

print(move([[0,0]]))

 

배운점

c#코드가 stackoverflow가 발생한다.. 로그를 배열이 아닌 리스트로 담고 있는 차이인데.. vs 스택사이즈 설정을 확인하려고 속성창에 들어가는데;; 안 보인다... 프로젝트 생성할떄 잘못된건지.. 버전문제인지 잘 모르겠다. 보면 볼수록 파이썬이 코드가 직관적이고 유연성이 좋아보인다.. 컬렉션 추가도 간단한 연산처리 처럼 되니.. 파이썬하다가 불편해서 다른 언어 쓰겠나..