[프로그래머스][python] 지게차와 크레인

 

작년에 응시한 하나은행 코딩테스트와 문제가 유사하다. (사실 예제까지 동일한 것 같다..!)

 

 

1차 시도

from collections import deque

def dfs(grid, i, j, n, m): # 나가는 경로찾기 input: grid, point
    qu = deque()
    qu.append((i,j))
    while qu:
        x, y = qu.popleft()
        if x == 0 or x == n-1 or y == 0 or y == m-1:
            return True
        for ni, nj in [(x+1, y), (x-1,y), (x,y+1), (x,y-1)]:
            if grid[ni][nj] == "0":
                qu.append((ni,nj))
    return False

def solution(storage, requests):
    answer = 0
    n = len(storage)
    m = len(storage[0])
    storage = [list(s) for s in storage]
    
    grid = [['1']*m]*n
    
    for req in requests:
        for i in range(n):
            for j in range(m):
                if (len(req) == 1) & (storage[i][j] == req):
                    if dfs(grid, i, j, n, m):
                        storage[i][j] = "0"
                if (len(req) == 2) & (storage[i][j] == req[0]):
                    storage[i][j] = "0"
        grid = [["0" if y == "0" else "1" for y in x] for x in storage]
    
    return sum([x.count("1") for x in grid])

 

 

결과

 

visited를 확인하지 않았더니, 탐색이 아주 오래 걸린 것이었다.

또한 bfs를 했다면, visited가 없어도 탐색이 가능했을 것 같다.

 

2차 시도

from collections import deque, Counter

# def dfs(grid, i, j, n, m): # 나가는 경로찾기 input: grid, point
def bfs(grid, i, j, n, m):  # 나가는 경로 찾기 (BFS 사용)
    qu = deque([(i, j)])
    visited = set()  # 방문한 노드를 기록하여 중복 탐색을 피함
    visited.add((i, j))
    
    while qu:
        x, y = qu.popleft()
        if x == 0 or x == n-1 or y == 0 or y == m-1:
            return True
        for ni, nj in [(x+1, y), (x-1,y), (x,y+1), (x,y-1)]:
            if 0 <= ni < n and 0 <= nj < m and (ni, nj) not in visited and grid[ni][nj] == "0":
                visited.add((ni, nj))
                qu.append((ni, nj))
    return False

def solution(storage, requests):
    answer = 0
    n = len(storage)
    m = len(storage[0])
    storage = [list(s) for s in storage]
    
    grid = [['1']*m]*n
    
    for req in requests:
        for i in range(n):
            for j in range(m):
                if (len(req) == 1) & (storage[i][j] == req):
                    if bfs(grid, i, j, n, m):
                        storage[i][j] = "0"
                if (len(req) == 2) & (storage[i][j] == req[0]):
                    storage[i][j] = "0"
        grid = [["0" if y == "0" else "1" for y in x] for x in storage]
    
    counter = Counter([item for sublist in grid for item in sublist])
    return counter['1']

 

성공

 

 

 

 

 

 

 

출처

- https://school.programmers.co.kr/learn/courses/30/lessons/388353