본문 바로가기
알고리즘 & PS

[프로그래머스] 무인도 여행 (Lv 2)

by 다람이도토리 2023. 12. 27.

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

기초적인 BFS 문제이다. 별 거 없이 방문여부, 현재 좌표, 최대 길이, 지도 전체 등등 다 넘겨버리면 그만.

BFS 사용 자체가 간만이라 기초 연습문제로 몸풀기.

# bfs 풀이가 필요함
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(maps, i, j, n, m, visit):
    queue = deque()
    queue.append((i, j))
    visit[i][j] = 1
    area = int(maps[i][j])
    while queue:
        x, y = queue.popleft()
        for d in range(4):
            # 새로운 좌표로 한 칸 이동
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < n and 0 <= ny < m:
                # 유효한 좌표 범위일 때, 방문 여부와 지도 유효화를 넣는다.
                if visit[nx][ny] == 0 and maps[nx][ny] != 'X':
                    # 방문한 적도 없고, 지도도 숫자가 있으면 원하는 행동을 하고 방문여부를 넣는다.
                    # 두 번 들틸 필요는 없으니까.
                    visit[nx][ny] = 1
                    area += int(maps[nx][ny])
                    queue.append((nx, ny))
    return area

def solution(maps):
    # n은 y축 개수, m은 x축 개수로 하자.
    n, m = len(maps), len(maps[0])
    # 방문 여부를 담아서 방문을 할지 말지를 결정하게 하자.
    visit = [[0] * m for _ in range(n)]
    answer = []
    
    # 좌표를 순서대로 탐색해서, 방문한 적이 없고, X도 아닐 경우 방문을 시작하자.
    for i in range(n):
        for j in range(m):
            if maps[i][j] != 'X' and visit[i][j] == 0:
                #넣을 때 시작좌표랑 전체 판 사이즈랑, 방문 여부랑 지도 전체를 넘겨야함
                answer.append(bfs(maps, i, j, n, m, visit))
                
    if len(answer) > 0:
        return sorted(answer)
    else:
        return [-1]