글 읽기 - 반례가 있을까요? 고수님들 도와주세요

you88311 6년 전 0

반례나 틀린점 지적 부탁드립니다

감사합니다

class Maze:
    def __init__(self,N,M):
        self.map = [[0 for i in range(M)] for j in range(N)]
        self.is_searched = [[False for i in range(M)] for j in range(N)]
        self.distance = [[0 for i in range(M)] for j in range(N)]

    def adj(self, i, j):
        adj_node = []
        if can_search(self.is_searched, self.map, i, j+1):
            adj_node.append([i, j+1])
        if can_search(self.is_searched, self.map, i-1, j):
            adj_node.append([i-1, j])
        if can_search(self.is_searched, self.map, i+1, j):
            adj_node.append([i+1, j])

        return adj_node

class Queue:
    def __init__(self):
        self.saved = []

    def insert(self,data):
        self.saved.append(data)

    def delete(self):
        return self.saved.pop(0)

    def is_empty(self):
        if len(self.saved) == 0:
            return True
        else:
            return False

def bfs(maze,queue,N,M):
    queue.insert([0,0])
    maze.is_searched[0][0] = True
    maze.distance[0][0] = 1

    while not queue.is_empty():
        tmp = queue.delete()
        i, j = tmp[0], tmp[1]
        distance = maze.distance[i][j]
        if des_reached(i, j ,N, M):
            break
        for adj in maze.adj(i,j):
            queue.insert(adj)
            a,b = adj[0] , adj[1]
            maze.distance[a][b] = distance+1
            maze.is_searched[a][b] = True

    return maze.distance[i][j]

def can_search(is_searched,map,i,j):
    if i >= N or j >= M or i<0 or j<0: #미로 범위 초과
        return False
    if is_searched[i][j] == True:
        return False
    if map[i][j] == 0:
        return False
    return True

def des_reached(i, j, N, M):
    if i==N-1 and j==M-1:
        return True

############################################
N , M= map(int,input().rstrip().split())
maze = Maze(N,M)
queue = Queue()

for i in range(N):
    input_ = list(input().rstrip())
    for j in range(M):
        maze.map[i][j] = int(input_[j])

shortest = bfs(maze,queue,N,M)
print(shortest)

you88311 6년 전 0

bfs함수 return에서 index를 [N-1][M-1]로 바꾸는게 맞는 것 같습니다 그래도 여전히 통과는 못하네요 허허허 ㅎㅎㅎㅎ

you88311 6년 전 0

해결했습니다! 왼쪽으로 가는 것을 고려 안했네요 ..최단거리여서 왼쪽은 무시하면 될줄 알았는데 착각이였습니다

jh05013 6년 전 0

이미 푸셨지만 매우 중요한 문제가 있습니다.

https://www.acmicpc.net/blog/v...
"list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 O(N)입니다. 절대로 list를 큐처럼 쓰지 마세요. collections.deque를 써야 합니다."

you88311 6년 전 0

오오 이런게 있었군요 감사합니다.

그럼 stack도 list보다는 저 모듈을 쓰는게 맞는건가요??

jh05013 6년 전 0

pop(0) 말고 pop()은 O(1)입니다. pop(0)가 O(N)인 이유는 맨 앞 원소를 빼면서 나머지 원소를 하나씩 왼쪽으로 옮기기 때문이고, pop()를 할 때는 옮길 원소가 없어서 바로 됩니다. 그래서 스택은 list를 사용해도 충분합니다.

you88311 6년 전 0

정말 덕분에 많이 배웠습니다

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 있을까요? 고수님들 도와주세요

you88311 6년 전 0

you88311 6년 전 0

you88311 6년 전 0

jh05013 6년 전 0

you88311 6년 전 0

jh05013 6년 전 0

you88311 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말