파이썬 미로 생성 알고리즘 - paisseon milo saengseong algolijeum

문제


n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

파이썬 미로 생성 알고리즘 - paisseon milo saengseong algolijeum

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력


첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

예제 입력과 출력

파이썬 미로 생성 알고리즘 - paisseon milo saengseong algolijeum

정답

from collections import deque

n=int(input())
a=[list(map(int,input())) for i in range(n)]
ch=[[-1] * n for i in range(n)]

dx=[-1,0,1,0]
dy=[0,1,0,-1]

def bfs():
    de=deque()
    de.append([0,0])
    ch[0][0]=0 

    while de:
        x,y=de.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if ch[nx][ny] == -1:
                    if a[nx][ny] == 0:
                        ch[nx][ny]= ch[x][y] + 1
                        de.append([nx,ny])
                    else:
                        ch[nx][ny]= ch[x][y]
                        de.appendleft([nx,ny])
                       
bfs()
print(ch[n-1][n-1])

흰방에 도착하면 이동거리는 이전과 같고 먼저 흰방을 방문하기 위해 appendleft를 사용합니다.
검은방에 도착하면 이동거리는 이전에서 +1해주고 append를 사용합니다.

백준 1261 알고스팟과 똑같은 문제입니다.


백준 알고리즘 2665번 : https://www.acmicpc.net/problem/2665

2665번: 미로만들기

첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

www.acmicpc.net

파이썬 미로 생성 알고리즘 - paisseon milo saengseong algolijeum

파이썬 미로 생성 알고리즘 - paisseon milo saengseong algolijeum
https://www.acmicpc.net/problem/2665
# 미로만들기
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

arr = []
for i in range(N):
    arr.append(list(map(int, input().strip())))


def bfs():
    q = deque()
    q.append((0, 0))
    visited = [[-1] * N for _ in range(N)]
    visited[0][0] = 0
    while q:
        x, y = q.popleft()
        if x == N-1 and y == N-1:
            return visited[x][y]
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == -1:
                if arr[nx][ny] == 1:
                    q.appendleft((nx, ny))
                    visited[nx][ny] = visited[x][y]
                else:
                    q.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1


print(bfs())

BFS

1. 시작지점(0, 0)에서 bfs를 한다. (visited = 검은 방을 흰 방으로 바꾼 횟수)

    - 해당 위치가 흰 방(1)이면 이전 visited의 값으로 초기화, appendleft(흰 방 먼저 탐색)

    - 해당 위치가 검은 방(0)이면 이전 visited에서 1을 더해서 초기화, append

2. x, y 가 도착지점(N-1, N-1)이면 return visited[x][y]

흰 방을 먼저 탐색하기 때문에

처음 도착지점에 도착한 visited의 값은 최솟값이 된다.

mimi_s.ico

0.12MB

이번엔 저번에 구현했던 미로 게임을 나름 업그레이드해봤다.

https://jinho-study.tistory.com/1081

기본적인 게임 개발 기술(실시간 처리, 키 입력 받기, 미로 게임)

이번엔 tkinter를 사용해서 기본적인 게임 개발 기술(실시간 처리, 키 입력 받기, 미로 게임)에 대해 알아보자. 1 실시간 처리 구현하기 파이썬에서는 after() 명령으로 실시간 처리를 수행할 수 있다

jinho-study.tistory.com

파이썬 미로 생성 알고리즘 - paisseon milo saengseong algolijeum

전체 코드는 아래와 같다.

import tkinter
import tkinter.messagebox


mx = 1 # 캐릭터의 가로 뱡향 위치를 관리하는 변수
my = 1 # 캐릭터의 세로 뱡향 위치를 관리하는 변수
state = 0 # 게임 상황, 0: 게임 진행, 1: 게임 클리어, 2: 게임 클리어 불가능
key = 0 # 키 이름을 입력할 변수 선언

# 키를 눌렀을 때 실행할 함수 정의
def key_down(e):
    global key # key을 전역 변수로 취급
    key = e.keysym # 눌려진 키 이름을 key에 대입
    
# 키를 눌렀다 뗐을 때 실행할 함수 정의
def key_up(e):
    global key # key을 전역 변수로 취급
    key = "" # key에 빈 문자열 대입

# 캐릭터 이동 함수
def move():
    global mx, my
    
    # key 방향이 통로라면 그 방향에 맞게 mx, my값을 변경
    if key == "Up" and maze[my-1][mx] == 0: 
        my -= 1
    if key == "Down" and maze[my+1][mx] == 0:
        my += 1
    if key == "Left" and maze[my][mx-1] == 0:
        mx -= 1
    if key == "Right" and maze[my][mx+1] == 0:
        mx += 1    
    
    # 캐릭터가 있는 장소가 벽이 아니라면 리스트 값을 2로 변경,
    # 칠한 회수를 1 증가시키고, 해당 위치를 분홍색으로 칠한다.
    if maze[my][mx] == 0:
        maze[my][mx] = 2
        # PAINT(지났던 길) 태그 추가
        canvas.create_rectangle(mx*80, my*80, mx*80 + 79, my*80 + 79, 
                                   fill="pink", width=0, tag="PAINT")
    canvas.delete("MYCHR")
    canvas.create_image(mx*80 + 40, my*80 + 40, image=img, tag="MYCHR") # 캐릭터 이미지 이동

# 칠해지지 않은 칸 수를 세주는 함수    
def count_tile():
    cnt = 0
    for i in range(7):
        for j in range(10):
            if maze[i][j] == 0:
                cnt += 1
    return cnt
    
# 게임 상태 확인 함수    
def check():
    cnt = count_tile()
    
    # 게임 클리어 불가능
    if 0 not in [maze[my-1][mx], maze[my+1][mx], maze[my][mx-1], maze[my][mx+1]]:
        return 2
    # 게임 클리어
    elif cnt == 0:
        return 1
    # 게임 진행
    else:
        return 0
        
# 게임 초기화 함수
def reset():
    global mx, my, state
    state = 0
    canvas.delete("PAINT")
    mx = 1
    my = 1
    for y in range(7):
        for x in range(10):
            if maze[y][x] == 2:
                maze[y][x] = 0
                
# 실시간 처리를 수행할 함수 정의
def main_proc():
    global mx, my, state, key
        
    # Esc 키를 누를 시 게임 종료
    if key == "Escape":
        key = 0
        ret = tkinter.messagebox.askyesno("종료", "게임을 종료하시겠습니까?")
        if ret == True:
            root.destroy()
            return ;
        
    # 왼쪽 Shift 키를 눌렀고 미로가 2칸 이상 칠해진 상태라면 게임 초기화
    if key == "Shift_L":
        reset()
                            
    state = check()
    # 게임 진행
    if state == 0:
        # 캐릭터 이동
        move()
    # 클리어 메시지를 표시해준 후에 게임 초기화
    if state == 1:
        canvas.update()
        tkinter.messagebox.showinfo("축하합니다!", "모든 바닥을 칠했습니다!")
        reset()
    # 클리어 불가능 메시지를 표시해준 후에 게임 초기화
    if state == 2:
        tkinter.messagebox.showinfo("망했어요!", "클리어가 불가능합니다\n 다시 시작하세요!")
        reset()
    
    root.after(100, main_proc)

    
root = tkinter.Tk()
root.title("미로를 칠하는 중")
root.bind("<KeyPress>", key_down)
root.bind("<KeyRelease>", key_up)
canvas = tkinter.Canvas(width=800, height=560, bg="white")
canvas.pack()

# 미로 생성
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 1, 0, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
for y in range(7):
    for x in range(10):
        if maze[y][x] == 1:
            canvas.create_rectangle(x * 80, y * 80, x * 80 + 79, y * 80 + 79, fill="skyblue", width=0)

img = tkinter.PhotoImage(file="mimi_s.png")
# MYCHR(캐릭터) 태그 추가
canvas.create_image(mx * 80 + 40, my * 80 + 40, image=img, tag="MYCHR")
main_proc()
root.mainloop()

게임 종료와 다시 시작 관련해서 기능을 추가하고 구조를 조금 수정했다. 

  • 0.2초 딜레이는 뭔가 답답해서 0.1초로 줄였다.
  • 게임을 클리어한 후에 Shift 키를 누르지 않아도 자동으로 게임을 초기화하고 다시 시작한다.
  • Esc 키를 입력받으면 yesorno 메시지 박스를 표시해주고 yes면 destroy() 명령을 사용해 게임을 종료시킨다.
  • yuka변수를 없애고 reset(게임 초기화), check(게임 상태 확인), count_tile(칠해지지 않은 칸 수 확인) 함수를 추가했다.
  • state 변수를 사용해서 게임 진행을 관리하는 식으로 메인 함수 구조를 수정했다.
    0: 게임 진행, 1: 게임 클리어, 2: 게임 클리어 불가능

게임 진행 관리 부분 코드

    state = check()
    # 게임 진행
    if state == 0:
        # 캐릭터 이동
        move()
    # 클리어 메시지를 표시해준 후에 게임 초기화
    if state == 1:
        canvas.update()
        tkinter.messagebox.showinfo("축하합니다!", "모든 바닥을 칠했습니다!")
        reset()
    # 클리어 불가능 메시지를 표시해준 후에 게임 초기화
    if state == 2:
        tkinter.messagebox.showinfo("망했어요!", "클리어가 불가능합니다\n 다시 시작하세요!")
        reset()

pyinstaller용 코드와 명령어

전체 코드

import tkinter
import tkinter.messagebox
import os


def resource_path(relative_path):
    try:
        base_path = sys._MEIPASS
    except Exception:
        base_path = os.path.abspath(".")
    return os.path.join(base_path, relative_path)

mx = 1 # 캐릭터의 가로 뱡향 위치를 관리하는 변수
my = 1 # 캐릭터의 세로 뱡향 위치를 관리하는 변수
state = 0 # 게임 상황, 0: 게임 진행, 1: 게임 클리어, 2: 게임 클리어 불가능
key = 0 # 키 이름을 입력할 변수 선언

# 키를 눌렀을 때 실행할 함수 정의
def key_down(e):
    global key # key을 전역 변수로 취급
    key = e.keysym # 눌려진 키 이름을 key에 대입
    
# 키를 눌렀다 뗐을 때 실행할 함수 정의
def key_up(e):
    global key # key을 전역 변수로 취급
    key = "" # key에 빈 문자열 대입

# 캐릭터 이동 함수
def move():
    global mx, my
    
    # key 방향이 통로라면 그 방향에 맞게 mx, my값을 변경
    if key == "Up" and maze[my-1][mx] == 0: 
        my -= 1
    if key == "Down" and maze[my+1][mx] == 0:
        my += 1
    if key == "Left" and maze[my][mx-1] == 0:
        mx -= 1
    if key == "Right" and maze[my][mx+1] == 0:
        mx += 1    
    
    # 캐릭터가 있는 장소가 벽이 아니라면 리스트 값을 2로 변경,
    # 칠한 회수를 1 증가시키고, 해당 위치를 분홍색으로 칠한다.
    if maze[my][mx] == 0:
        maze[my][mx] = 2
        # PAINT(지났던 길) 태그 추가
        canvas.create_rectangle(mx*80, my*80, mx*80 + 79, my*80 + 79, 
                                   fill="pink", width=0, tag="PAINT")
    canvas.delete("MYCHR")
    canvas.create_image(mx*80 + 40, my*80 + 40, image=img, tag="MYCHR") # 캐릭터 이미지 이동

# 칠해지지 않은 칸 수를 세주는 함수    
def count_tile():
    cnt = 0
    for i in range(7):
        for j in range(10):
            if maze[i][j] == 0:
                cnt += 1
    return cnt
    
# 게임 상태 확인 함수    
def check():
    cnt = count_tile()
    
    # 게임 클리어 불가능
    if 0 not in [maze[my-1][mx], maze[my+1][mx], maze[my][mx-1], maze[my][mx+1]]:
        return 2
    # 게임 클리어
    elif cnt == 0:
        return 1
    # 게임 진행
    else:
        return 0
        
# 게임 초기화 함수
def reset():
    global mx, my, state
    state = 0
    canvas.delete("PAINT")
    mx = 1
    my = 1
    for y in range(7):
        for x in range(10):
            if maze[y][x] == 2:
                maze[y][x] = 0
                
# 실시간 처리를 수행할 함수 정의
def main_proc():
    global mx, my, state, key
        
    # Esc 키를 누를 시 게임 종료
    if key == "Escape":
        key = 0
        ret = tkinter.messagebox.askyesno("종료", "게임을 종료하시겠습니까?")
        if ret == True:
            root.destroy()
            return ;
        
    # 왼쪽 Shift 키를 눌렀고 미로가 2칸 이상 칠해진 상태라면 게임 초기화
    if key == "Shift_L":
        reset()
                            
    state = check()
    # 게임 진행
    if state == 0:
        # 캐릭터 이동
        move()
    # 클리어 메시지를 표시해준 후에 게임 초기화
    if state == 1:
        canvas.update()
        tkinter.messagebox.showinfo("축하합니다!", "모든 바닥을 칠했습니다!")
        reset()
    # 클리어 불가능 메시지를 표시해준 후에 게임 초기화
    if state == 2:
        tkinter.messagebox.showinfo("망했어요!", "클리어가 불가능합니다\n 다시 시작하세요!")
        reset()
    
    root.after(100, main_proc)

    
root = tkinter.Tk()
root.title("미로를 칠하는 중")
root.bind("<KeyPress>", key_down)
root.bind("<KeyRelease>", key_up)
canvas = tkinter.Canvas(width=800, height=560, bg="white")
canvas.pack()

# 미로 생성
maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 1, 0, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
for y in range(7):
    for x in range(10):
        if maze[y][x] == 1:
            canvas.create_rectangle(x * 80, y * 80, x * 80 + 79, y * 80 + 79, fill="skyblue", width=0)

img = tkinter.PhotoImage(file=resource_path("mimi_s.png"))
# MYCHR(캐릭터) 태그 추가
canvas.create_image(mx * 80 + 40, my * 80 + 40, image=img, tag="MYCHR")
main_proc()
root.mainloop()

명령어

pyinstaller -w -F --add-data "mimi_s.png;." -i "mimi_s.ico" maze_game.py

github: https://github.com/kimjinho1/Python-Game/blob/main/%EA%B8%B0%EB%B3%B8%EC%A0%81%EC%9D%B8%20%EA%B2%8C%EC%9E%84%20%EA%B0%9C%EB%B0%9C%20%EA%B8%B0%EC%88%A0/maze_game.ipynb

kimjinho1/Python-Game

Contribute to kimjinho1/Python-Game development by creating an account on GitHub.

github.com

파이썬 미로 생성 알고리즘 - paisseon milo saengseong algolijeum