[leetcode] 3-10회차

책을 샀다. 행복하다. 

https://leetcode.com/problems/course-schedule-ii/?envType=study-plan-v2&envId=top-interview-150

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        self.graph = collections.defaultdict(list)
        self.res = []

        for pair in prerequisites:
            self.graph[pair[0]].append(pair[1])

        self.visited = [0 for x in xrange(numCourses)]

        for x in xrange(numCourses):
            if not self.DFS(x):
                return []
        return self.res

    def DFS(self, node):
        if self.visited[node] == -1:
            return False
        if self.visited[node] == 1:
            return True
        self.visited[node] = -1
        for x in self.graph[node]:
            if not self.DFS(x):
                return False        
        self.visited[node] = 1
        self.res.append(node)
        return True

 

어제 풀었던 문제와 크게 다르지 않은 문제였다. 

 

https://leetcode.com/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150

class Solution(object):
    def snakesAndLadders(self, board):
        """
        :type board: List[List[int]]
        :rtype: int
        """
        n = len(board)
        min_rolls = [-1] * (n * n + 1)
        q = deque()
        min_rolls[1] = 0
        q.append(1)

        while q:
            x = q.popleft()
            for i in range(1, 7):
                t = x + i
                if t > n * n:
                    break
                row = (t-1) //n
                col = (t-1) % n
                v = board[n-1 - row][(n-1-col) if (row % 2 ==1) else col]
                y =v if v > 0 else t
                if y == n * n:
                    return min_rolls[x] + 1
                if min_rolls[y] == -1:
                    min_rolls[y] = min_rolls[x] + 1
                    q.append(y)
                
        return -1