99클럽 코테 스터디 9일차 TIL + DFS/BFS

 

🔗 프로그래머스 - 게임 맵 최단거리

P.S | 해당 문제는 데크를 BFS로 이용해서 풀면 문제 답과 효율성 테스트를 통과할 수 있다!

이 방법으로도 시도해 보면서 알게 된점은!

효율성 테스트를 통과하려면 최대한 적은 경우의 수로 움직여 줘야 한다. 해당하지 않은 경로는 아예 가지 않도록 계속 조건을 줘야 함!

그리고

1) 간곳을 maps 에서 0으로 처리해 주면서 count를 따로 세는 방법과,

2) maps에 count를 저장하면서 실행하는 두가지 방법을 해봤는데

둘다 테스트 코드는 통과했지만 효율성은 2)만 통과했다....! 

---

이번주에 아는 선생님과 객체에 관해서 이야기를 나눴다. 

객체를 state를 저장하는 데 사용한다는 이야기를 했었는데 그것을 실제로 적용해 보고 싶었다. 

그래서 이번 코드를 객체를 이용해서 풀어보았다. 

DFS로 풀었는데 재귀를 돌때 새로운 객체를 만들어서 넘겨주는 방식을 사용했다. 

이 방법을 통해서 재귀와 더 친해진 느낌이 들어서 만족스러웠다. 

사실 효율성 테스트는 통과하지 못했는데 DFS로는 통과하지 못한다고 한다. 그래서 과감하게 포기하고 객체 사용에 집중했다. 

그리고 코드의 가독성을 높히기 위해 함수 이름이나 변수 이름을 조금 신경써 봤다. 😁

import numpy as np


class Player:
    def __init__(self, maps):
        self.current_y = 0
        self.current_x = 0
        self.last_move = ""
        self.move_count = 0
        self.maps = maps
        self.visited = [(self.current_y, self.current_x)]
        self.route_dists = []

    def moveUp(self):
        if (not self.out(self.current_y - 1, self.current_x) and self.last_move != "down"
                and self.maps[self.current_y - 1][self.current_x]):
            self.current_y -= 1
            self.last_move = "up"
            self.move_count += 1
            self.visited = self.visited + [(self.current_y, self.current_x)]
            return True
        return False

    def moveDown(self):
        if (not self.out(self.current_y + 1, self.current_x) and self.last_move != "up"
                and self.maps[self.current_y + 1][self.current_x]):
            self.current_y += 1
            self.last_move = "down"
            self.move_count += 1
            self.visited = self.visited + [(self.current_y, self.current_x)]
            return True
        return False

    def moveRight(self):
        if (not self.out(self.current_y, self.current_x + 1) and self.last_move != "left"
                and self.maps[self.current_y][self.current_x + 1]):
            self.current_x += 1
            self.last_move = "right"
            self.move_count += 1
            self.visited = self.visited + [(self.current_y, self.current_x)]
            return True
        return False

    def moveLeft(self):
        if (not self.out(self.current_y, self.current_x - 1) and self.last_move != "right"
                and self.maps[self.current_y][self.current_x - 1]):
            self.current_x -= 1
            self.last_move = "left"
            self.move_count += 1
            self.visited = self.visited + [(self.current_y, self.current_x)]
            return True
        return False

    # 게임판을 나간경우
    def out(self, x, y):
        if self.maps.shape[0] - 1 < x or x < 0:
            return True
        if self.maps.shape[1] - 1 < y or y < 0:
            return True
        return False

    def cantMove(self):
        count = 0
        if 0 <= self.current_y - 1 <= self.maps.shape[0] - 1 and (self.maps[self.current_y - 1][self.current_x] or (
                self.current_y, self.current_x) not in self.visited):
            count += 1
        if 0 <= self.current_y + 1 <= self.maps.shape[0] - 1 and (self.maps[self.current_y + 1][self.current_x] or (
                self.current_y + 1, self.current_x) not in self.visited):
            count += 1
        if 0 <= self.current_x + 1 <= self.maps.shape[1] - 1 and (self.maps[self.current_y][self.current_x + 1] or (
                self.current_y, self.current_x + 1) not in self.visited):
            count += 1
        if 0 <= self.current_x - 1 <= self.maps.shape[1] - 1 and (self.maps[self.current_y][self.current_x - 1] or (
                self.current_y, self.current_x - 1) not in self.visited):
            count += 1
        if count > 0:
            return False
        else:
            return True

    def find_route(self, player):
        # print("x:", player.current_x, "y:", player.current_y, "dists:", player.route_dists, "visited", player.visited)
        if player.current_y == (player.maps.shape[0] - 1) and player.current_x == (player.maps.shape[1] - 1):
            return [player.move_count + 1]
        if player.cantMove():
            return -1
        for i in range(4):
            # 위로 가기
            if i == 0 and (player.current_y - 1, player.current_x) not in player.visited:
                new_player = copyClass(player.maps, player)
                if new_player.moveUp():
                    player.route_dists += self.find_route(new_player)

            # 아래로 가기
            if i == 1 and (player.current_y + 1, player.current_x) not in player.visited:
                new_player = copyClass(player.maps, player)
                if new_player.moveDown():
                    player.route_dists += self.find_route(new_player)
            # 오른쪽으로 가기
            if i == 2 and (player.current_y, player.current_x + 1) not in player.visited:
                new_player = copyClass(player.maps, player)
                if new_player.moveRight():
                    player.route_dists += self.find_route(new_player)
            # 왼쪽으로 가기
            if i == 3 and (player.current_y, player.current_x - 1) not in player.visited:
                new_player = copyClass(player.maps, player)
                if new_player.moveLeft():
                    player.route_dists += self.find_route(new_player)
        return player.route_dists


def copyClass(maps, player):
    new = Player(maps[:])
    new.current_y = player.current_y
    new.current_x = player.current_x
    new.move_count = player.move_count
    new.visited = player.visited
    return new


def solution(maps):
    maps = np.array(maps)
    player_init = Player(maps)
    answer = player_init.find_route(player_init)
    if -1 in answer or not len(answer):
        return -1
    return min(answer)