HackerRank - Castle on the Grid

문제 : https://www.hackerrank.com/challenges/castle-on-the-grid/problem

 

코드 : 

BFS의 응용 버전

두번째 코드 (성공!)

from collections import deque
def minimumMoves(grid, startX, startY, goalX, goalY):
    n = len(grid)
    m = len(grid[0])
    maximum = n*m
    # n*m graph
    graph = [[maximum]*m for _ in range(n)]
    graph[startX][startY] = 0
    
    # for debugging
    def printGraph():
        print('====printGraph=====')
        for i in range(n):
            for j in range(m):
                print(graph[i][j], end=' ')
            print(" ")
    
    #BFS visit all - queue
    dr = [-1, 1, 0, 0] # top, bottom, left, right
    dc = [0, 0, -1, 1]
    
    queue = deque()
    queue.append((startX, startY))
    while queue:
        r, c = queue.popleft()
        for d in range(4):
            nr = r
            nc = c
            while True:
                nr = nr +dr[d]
                nc = nc +dc[d]
                #check out of boundary
                if nr<0 or nr>=n or nc<0 or nc>=m:
                    break
                #check wall
                if grid[nr][nc] == 'X':
                    break
                #check
                if graph[nr][nc] > graph[r][c]+1 :
                    graph[nr][nc] = graph[r][c]+1
                    queue.append((nr,nc))
        #printGraph()
    return graph[goalX][goalY]

첫번째 틀렸던 코드와의 가장 큰 차이점은 해당 노드에 방문여부 차이

틀린 코드는 이미 방문했던 노드이면 최소거리 계산을 안했는데

맞은 코드에서는 기존 최소거리보다 더 작아지면 업데이트해줌

 

 

처음에 해결 방법 (실패)

14개의 테스트 문제중 1개를 실패함 (2번 테스트케이스 실패함)

2번 테스트 케이스의 정답은 13인데 내꺼는 14 출력함 ㅠㅠ

원인 못찾음

from collections import deque
def minimumMoves(grid, startX, startY, goalX, goalY):
    n = len(grid)
    m = len(grid[0])
    maximum = n*m
    # n*m graph
    graph = [[maximum]*m for _ in range(n)]
    graph[startX][startY] = 0
    
    # for debugging
    def printGraph():
        print('====printGraph=====')
        for i in range(n):
            for j in range(m):
                print(graph[i][j], end=' ')
            print(" ")
    
    #BFS visit all - queue
    dr = [-1, 1, 0, 0] # top, bottom, left, right
    dc = [0, 0, -1, 1]
    
    queue = deque()
    queue.append((startX, startY))
    while queue:
        r, c = queue.popleft()
        for d in range(4):
            nr = r
            nc = c
            while True:
                nr = nr +dr[d]
                nc = nc +dc[d]
                #check out of boundary
                if nr<0 or nr>=n or nc<0 or nc>=m:
                    break
                #check visited
                if graph[nr][nc] != maximum:
                    break
                #check wall
                if grid[nr][nc] == 'X':
                    break
                graph[nr][nc] = graph[r][c]+1
                queue.append((nr,nc))
        #printGraph()
    return graph[goalX][goalY]

 

다른 사람 코드 : 

row, column , vlaue 좌표랑 최소거리값을 함께 쌍을 지어서 리스트에 넣는게 재미있었음

그리고 visited 2차원 배열을 따로 저장하지 않고 좌표를 넣어서 그 리스트에 들어있는지 확인하는것도 새로움 (근데 이게 더 느리려나? )

 

그리고 이사람도 나랑 같이 goal 에 갈 수 있는 path가 여러가지라면 최소 길이를 반환할 수 있을지 모르겠음

똑같이 testcase2 해봤는데 옳은 정답 13 나옴! 왜지??????///

 

def minimumMoves(mat, strow, stcol, gorow, gocol):
    rows = len(mat)
    cols = len(mat[0])
    moves = ((1,0), (-1,0), (0,-1), (0,1)) #bottom top left right
    visit = {(strow, stcol)}
    q = [[strow, stcol, 0]]
    while len(q)>0:
        path, q = q[0], q[1:]
        row, col, val = path
        for move in moves:
            nrow, ncol = row, col
            while True:
                nrow, ncol = nrow+move[0], ncol+move[1]
                if nrow>=0 and ncol>=0 and nrow<rows and ncol<cols and mat[nrow][ncol] == '.':
                    if(nrow, ncol) == (gorow, gocol):
                        return val+1
                    else :
                        if(nrow, ncol) not in visit:
                            visit.add((nrow, ncol))
                            q += [[nrow, ncol, val+1]]
                else:
                    break
    return -1