[프로그래머스] Level2 무인도 여행(python)

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

프로그래머스

 

1. 내가 작성한 코드

from collections import deque

def bfs(i,maps,visit):
    
    cnt = int(maps[i[0]][i[1]]) #첫 방문 위치의 식량
    visit[i[0]][i[1]] = 1
    queue = deque()
    queue.append(i)
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx<0 or ny<0 or nx>=len(maps) or ny>=len(maps[0]): #maps의 범위를 넘어가면 정지
                continue
                
            if maps[nx][ny] == "X": #바다를 만나면 정지
                continue
            
            if visit[nx][ny] == 0:
                visit[nx][ny] = 1
                cnt += int(maps[nx][ny])
                queue.append((nx,ny))
    return cnt           
    

def solution(maps):
    answer = []
    island = [] #섬의 좌표
    visit = [[0] * len(maps[0]) for _ in range(len(maps))]
    
    for i in range(len(maps)): #바다가 아닌 좌표를 island에 append
        for j in range(len(maps[0])):
            if maps[i][j] != "X":
                island.append((i,j))
                
    if len(island) == 0: #섬의 개수가 0일 경우 -1
        return [-1]
    
    for i in island:
        if visit[i[0]][i[1]] == 0:
            answer.append(bfs(i,maps,visit))
    
    return sorted(answer)

 

 

2. 문제해결 방법

BFS를 이용해서 해결했다.

 

solution 함수

 

1. maps를 탐색하며 X 즉, 바다가 아닌 부분을 island라는 새로운 list에 삽입한다.

 

def solution(maps):
    answer = []
    island = [] #섬의 좌표
    visit = [[0] * len(maps[0]) for _ in range(len(maps))]
    
    for i in range(len(maps)): #바다가 아닌 좌표를 island에 append
        for j in range(len(maps[0])):
            if maps[i][j] != "X":
                island.append((i,j))

 

2. island의 list 길이가 0인 경우는 섬이 하나도 없는 것이기 때문에 -1를 return 한다.

 

  if len(island) == 0: #섬의 개수가 0일 경우 -1
        return [-1]

 

3. island list를 탐색하며 방문하지 않은 곳을 bfs의 인자에 넣고 함수를 실행시킨다. 이때, return 되는 값(총 식량 수)을 answer에다 삽입한다.

 

for i in island:
        if visit[i[0]][i[1]] == 0:
            answer.append(bfs(i,maps,visit))

 

4. answer을 정렬시키고 최종으로 return한다.

 

 

 

BFS함수

 

1. bfs에 들어오는 i는 아직 방문하지 않은 섬의 좌표이다. visit의 i좌표를 방문처리 해주고, cnt 변수에 첫 방문 위치 식량을 더해준다. (maps에는 문자열로 삽입되어 있어서 int로 변환하는 과정이 필요했다)

from collections import deque

def bfs(i,maps,visit):
    
    cnt = int(maps[i[0]][i[1]]) #첫 방문 위치의 식량
    visit[i[0]][i[1]] = 1
    queue = deque()
    queue.append(i)

 

2. 상하좌우 네 방향을 도는 nx,ny 좌표를 만들어준다.

 

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

 

3. maps의 범위를 넘어가거나 바다를 만다면 continue 해준다.

 

상하좌우에 방문하지 않은 곳이 있다면 방문 처리를 해주고, 그 위치에 있는 식량을 cnt 에 더해준다.

 

이 nx,ny 값을 queue에 삽입해줌으로써 현위치에서 부터 bfs를 다시 돌게해준다.

 

  if nx<0 or ny<0 or nx>=len(maps) or ny>=len(maps[0]): #maps의 범위를 넘어가면 정지
                continue
                
            if maps[nx][ny] == "X": #바다를 만나면 정지
                continue
            
            if visit[nx][ny] == 0:
                visit[nx][ny] = 1
                cnt += int(maps[nx][ny])
                queue.append((nx,ny))
    return cnt

 

4. while문이 끝났을 때(=queue에 아무런 원소가 없을 때)는 이어져 있는 모든 위치를 방문처리 한 것을 의미함으로 cnt(식량 수)를 return해준다.