백준 4991. 로봇 청소기(python)

• 4991. 로봇 청소기

4991번: 로봇 청소기

---

입력

• 입력으로 첫 줄에 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20)
• 둘째 줄부터 h개의 줄에 방의 정보가 주어진다.
• 방의 정보는 문자로 들어오며 각각의 문자와 그 의미는 아래와 같다.
• '.' : 깨끗한 칸, '*' : 더러운 칸, 'x' : 가구, 'o' : 로봇 청소기의 시작 위치
• 더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기는 항상 하나이다.
• 입력의 마지막 줄에는 0이 두 개 주어진다.

---

문제 풀이

• 로봇 청소기의 위치 및 더러운 칸들 간의 거리를 구한 후, 순열을 사용해 풀이했다.

while 1:
    M, N = [*map(int, input().split())]
    if M == 0 and N == 0:
        break

    room = [0]*N
    flag = 0
    info = []
    cnt = 1
    minn = 21e10

    for i in range(N):
        room[i] = list(input().rstrip())        # 방 정보// . : 깨끗, * : 더러움, x : 가구, o : 로봇 청소기 시작 위치

    for i in range(N):
        for j in range(M):
            if room[i][j] == 'o':           # 시작 위치 체크
                info.append([0, i, j])
                room[i][j] = 0              # 청소기 시작 위치 0번 위치로 바꿈
            elif room[i][j] == '*':         # 더러운 칸 체크
                info.append([cnt, i, j])
                room[i][j] = cnt            # 각 더러운 칸들 숫자로 바꿈
                cnt += 1

• 먼저 입력의 개수가 주어지지 않으므로 w, h 변수에 각각 0을 입력받을 때까지 while문을 돌린다.
• 좀 더 쉽게 구분하기 위하여 이중 for문을 통하여 청소기 시작 위치와 더러운 칸에 번호를 붙여준다.(청소기 위치-0)

    arr = [[0 for _ in range(cnt)] for _ in range(cnt)]     # 청소기 위치 또는 더러운 칸 사이의 거리들 저장할 리스트
    info = sorted(info, key=lambda x:x[0])                  # 빠른 번호 순서로 정렬

• 각 숫자를 붙여준 위치들을 리스트에 저장한 후 빠른 번호 순서로 정렬한다.

    for i in info:
        bfs(i[1], i[2], cnt)        # 앞서 체크한 위치에서 다른 위치까지 거리 구하기 위해 bfs
        if flag == 1:
            break

• 위에서 저장한 각 위치에 대해서 bfs를 통해 다른 위치까지의 거리를 구한다.
• 해당 함수 구조는 아래와 같다.

def bfs(y, x, cnt):         # cnt - 청소기 위치 + 더러운칸 개수
    global flag
    check_num = cnt
    visited = [[-1 for _ in range(M)] for _ in range(N)]
    queue = deque()
    queue.append((y, x))
    visited[y][x] = 0
    while queue:
        now = queue.popleft()
        for i in range(4):
            ny = now[0] + dy[i]
            nx = now[1] + dx[i]
            if 0 <= ny < N and 0 <= nx < M:
                if visited[ny][nx] == -1 and room[ny][nx] != 'x':
                    visited[ny][nx] = visited[now[0]][now[1]] + 1
                    queue.append((ny, nx))
                    if room[ny][nx] != '.':
                        arr[room[y][x]][room[ny][nx]] = visited[ny][nx]     # 다른 번호 위치 도착하면 거리 저장
                        check_num -= 1      # 다른 위치(더러운 칸, 청소기) 도착할 때마다 -1
        if check_num == 1:
            break
    if check_num > 1:   # 방문 못한 칸 있으면 flag 킴
        flag = 1
        return

• visited 리스트로 해당 칸에서 다른 칸까지의 거리를 구한다.
• 만약 가지 못한 칸이 있다면 flag에 1을 할당한다.

    if flag == 1:           # flag 켜졌으면 불가능
        print(-1)
    else:
        used = [0]*cnt
        used[0] = 1
        dfs(0, 0, cnt, 0)   # 앞서 bfs 통해 구해놓은 거리 리스트를 조합하여 최단거리 찾기위해 dfs
        print(minn)

• 만약 flag가 1이면 이어지지 못한 칸이 있으므로, -1 출력한다.
• 아니라면 위의 bfs에서 구한 거리 리스트와 dfs를 이용하여 최단 거리 조합을 구한 후 출력한다.
• dfs 함수의 구조는 아래와 같다.

def dfs(v, level, cnt, sum):
    global minn
    if sum > minn:
        return
    if level == cnt-1:
        if minn > sum:
            minn = sum
        return
    for i in range(1, cnt):
        if used[i] == 0:
            used[i] = 1
            dfs(i, level+1, cnt, sum+arr[v][i])
            used[i] = 0

• 더러운 칸을 모두 연결했으면 기존의 거리 합과 비교하여 갱신
• 중간 과정에서의 거리 합이 기존의 합보다 크면 리턴하여 시간을 줄일 수 있다.