Home [Master The Simulation 인구이동] Python 풀이시 시간초과 발생이유 및 해결책
Post
Cancel

[Master The Simulation 인구이동] Python 풀이시 시간초과 발생이유 및 해결책

Python 풀이시 시간초과 발생이유 및 해결책

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from collections import defaultdict,deque
from copy import deepcopy

class Solution:
    
    def checkBound(self,r,c):
        if r < 0 or r > self.n-1 or c < 0 or c > self.n-1:
            return False
        return True
    
    def checkMove(self,pos1,pos2):
        p1 = self.map[pos1[0]][pos1[1]]
        p2 = self.map[pos2[0]][pos2[1]]
        diff = abs(p1-p2)
        if diff >= self.l and diff <= self.r:
            return True
        else:
            return False

    def bfs(self,start):
        traversed = defaultdict(int)
        summ = 0
        que = deque()
        que.append(start)
        isAdded = defaultdict(int)
        self.visited[start] = 1
        while len(que) > 0:
            front = que[0]
            traversed[front] = 1
            if isAdded[front] == 0:
                summ += self.map[front[0]][front[1]]
                isAdded[front] = 1
            que.popleft()
            for i in range(4):
                nextPos = (front[0]+self.offset[i][0],front[1]+self.offset[i][1])
                if self.checkBound(nextPos[0],nextPos[1]) and self.visited[nextPos] == 0 and self.checkMove(front,nextPos):
                    que.append(nextPos)
                    self.visited[nextPos] = 1
                    
        for node in traversed:
            self.newMap[node[0]][node[1]] = summ//len(traversed)
        return len(traversed) > 1
        
    def solve(self):
        self.n,self.l,self.r = [int(i) for i in input().split()]
        self.map = []
        for _ in range(self.n):
            line = [int(j) for j in input().split()]
            self.map.append(line)
        self.offset = [(0,1),(0,-1),(1,0),(-1,0)]
        res = 0
        
        while True:
            self.visited = defaultdict(int)
            flag = True
            self.newMap = deepcopy(self.map)
            for i in range(self.n):
                for j in range(self.n):
                    if self.visited[(i,j)] == 0:
                        if self.bfs((i,j)):
                            flag = False
            if flag:
                break
            self.map = self.newMap
            res += 1
        print(res)
Solution().solve()
  1. BFS시 que에 넣는 동시에 visited 배열을 갱신하지 않으면 동일 노드가 큐에 들어간다.
  2. queue를 사용시 list를 사용 append,pop을 할때 O(n) 시간 소요
    해결법은 deque를 사용한다.

그외에 여러 해결책은 다음글을 읽어보면 도움이된다.

This post is licensed under CC BY 4.0 by the author.

Order of execution of a Query (쿼리의 실행순서)

Hackerrank - Java Regex 2 - Duplicate Words Solution 해설

Comments powered by Disqus.

Trending Tags