[알고리즘] 실습용 로봇, 석유 시추, 보물 지도

실습용 로봇

방향성을 다루는 부분을 단순하게 표현하기만 하면 금방 푸는 문제.

 

내 풀이

def solution(command):
    x, y = 0, 0
    dir_x, dir_y = 0, 1
    
    for com in command:
        if com == 'G': x, y = x+dir_x, y+dir_y
        elif com == 'B': x, y = x-dir_x, y-dir_y
        elif com == 'R': dir_x, dir_y = dir_y, -dir_x
        else: dir_x, dir_y = -dir_y, dir_x        
    
    return [x, y]

 

 

석유 시추

2D를 traverse 하다가, 기름이 나타나면 그 기름이 속한 덩어리를 파헤치러 dfs 써주는 문제.

dfs를 하는 과정에서 그 덩어리의 이름도 명명하고, 사이즈도 찾아주고, 속한 모든 성분에 네이밍도 해주고.

이 발상 자체는 맞았고, 정확성 테스트도 통과했지만 효율성에서 절망.

 

효율성의 모든 문제가 틀렸지만, TLE가 아닌 런타임 에러가 뜸.

그래서 찾아보니 모든 코드는 재귀의 뎁스를 제한해놨고, 그게 파이썬의 경우 1000이라 그에 걸린 듯.

그래서 재귀를 반복문 (stack 활용) 으로 바꿔줬더니 같은 로직인데도 통과함.

 

★ 결론은, dfs를 구현할 때는 가급적 재귀보다는 반복문을 쓰자. 재귀를 쓸 이유가 없다.

stack을 쓰기 때문에 list에 append, pop 하는 게 함수 호출보다 빠른 데다가, recursion limit도 없음.

JAVA도 제한이 있지만, 횟수로 정해진 게 아니라 JVM의 용량에 좌우됨 - 보통 5000~10000 회.

 

내 풀이

def solution(land):
    dungs = {}
    ind = 2
    
    def traverse(x, y, ind, land):
        dirs = [[0,1],[0,-1],[1,0],[-1,0]]
        size = 1
        land[x][y] = ind
        
        for di_x, di_y in dirs:
            n_x, n_y = x+di_x, y+di_y
            if 0 <= n_x < len(land) and 0 <= n_y < len(land[0]):
                if land[n_x][n_y] == 1:
                    size += traverse(n_x, n_y, ind, land)
        
        return size
    
    for i in range(len(land)):
        for j in range(len(land[0])):
            if land[i][j] == 1:
                # 해당 덩어리 모두 돌고 넘버링 함 (넘버링은 2부터 시작)
                # 다 끝나면 크기값을 dungs에 저장함
                dungs[ind] = traverse(i, j, ind, land)
                ind += 1
    
    res = 0
    
    for i in zip(*land):
        temp = 0
        for j in set(i): 
            if j: temp += dungs[j]
        if res < temp: res = temp
    
    return res

 

여기서 traverse 함수를 아래와 같이 반복문으로 바꾸면 된다.

    def traverse(x, y, ind):
        stack = [(x, y)]
        size = 0
        while stack:
            cx, cy = stack.pop()
            if land[cx][cy] == 1:  # 석유 덩어리를 찾으면
                size += 1
                land[cx][cy] = ind  # 방문 처리 및 ID 할당
                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    nx, ny = cx + dx, cy + dy
                    if 0 <= nx < len(land) and 0 <= ny < len(land[0]) and land[nx][ny] == 1:
                        stack.append((nx, ny))
        return size

 

 

보물 지도

bfs 쓴 구현 문제. 인덱싱도 바꿔주고, 점프를 사용한 경우 / 아닌 경우의 두 경로를 track 하므로 3D 리스트 활용.

포기할 뻔~

from collections import deque

def solution(n, m, hole):    
    res = float('inf')

    stat_table = [[[float('inf'), float('inf')] for _ in range(n)] for _ in range(m)]   # jump o, x
    
    for hx, hy in hole: stat_table[m-hy][hx-1] = [-1,-1]
            
    queue = deque([(m-1, 0, 0, True)])       # x, y, 해당 점까지의 최단거리, 점프여부
    stat_table[m-1][0][0] = 0
    
    while queue:
        x, y, cur_dis, jump = queue.popleft()
        
        for dx, dy in [[-1,0], [1,0], [0,-1], [0,1]]:
            nx, ny = x+dx, y+dy
            
            if 0 <= nx < m and 0 <= ny < n:
                if nx == 0 and ny == n-1:
                    if jump: res = min(res, cur_dis)
                    else: res = min(res, cur_dis+1)
                else:
                    if stat_table[nx][ny][0] != -1:
                        if jump:
                            if stat_table[nx][ny][0] > cur_dis+1:
                                stat_table[nx][ny][0] = cur_dis+1
                                queue.append([nx,ny,cur_dis+1,jump])
                        elif not jump:
                            if stat_table[nx][ny][1] > cur_dis+1:
                                stat_table[nx][ny][1] = cur_dis+1
                                queue.append([nx,ny,cur_dis+1,jump])
                    elif jump:
                        nx += dx
                        ny += dy
                        if 0 <= nx < m and 0 <= ny < n and stat_table[nx][ny][1] > cur_dis+1:
                            stat_table[nx][ny][1] = cur_dis+1
                            queue.append([nx,ny,cur_dis+1,False])
    
    return res if res != float('inf') else -1