프로그래머스)무인도 여행

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

프로그래머스

 

 

 

처음 제출한 코드

def solution(maps):
    answer = []
    
    visit = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
    
    answer = []
    
    
    
    dx = [1,-1,0,0]
    dy = [0,0,-1,1]
    def dfs(x,y,cnt):
        visit[x][y] = True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (0 <= nx < len(maps)) and (0 <= ny < len(maps[0])) and maps[nx][ny] != 'X':
                if visit[nx][ny] == False:
                    cnt = dfs(nx,ny,cnt + int(maps[nx][ny]))
        return cnt
        
    
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            cnt = 0
            if visit[i][j] == False:
                if maps[i][j] != 'X':
                    cnt = dfs(i,j,int(maps[i][j]))
                    
                    answer.append(cnt)

    answer.sort()
    return [-1] if len(answer) == 0 else  answer

전형적인 dfs bfs 문제지만 

이런 문제를 봤을 때 제한사항을 살피지 않고 무작정 dfs로 푸는 경향이 내게는 조금 있는 듯 하다.

역시나 시간초과로 실패했다.

그래서 bfs로 바꾸어서 풀어보았다.

from collections import deque

def solution(maps):
    answer = []
    visit = [[False for _ in range(len(maps[0]))] for _ in range(len(maps))]
    dx = [1,-1,0,0]
    dy = [0,0,-1,1]
    
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if visit[i][j] == False and maps[i][j] != 'X':
                visit[i][j] = True
                num = 0 
                q = deque()
                q.append((i,j))
                while q:
                    
                    x,y = q.popleft()
                    num = num + int(maps[x][y])
                    for k in range(4):
                        nx = dx[k] + x
                        ny = dy[k] + y
                        if (0 <= nx < len(maps)) and (0 <= ny < len(maps[0])):
                            if maps[nx][ny] != 'X' and visit[nx][ny] == False:
                                visit[nx][ny] = True
                                q.append((nx,ny))
                answer.append(num)
    answer.sort()
    return answer if len(answer) >0 else [-1]

무난하게 통과!