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

문제

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

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

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

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

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

입력

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

출력

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

예제 입력과 출력

정답

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번 : //www.acmicpc.net/problem/2665

2665번: 미로만들기

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

www.acmicpc.net

//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

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

//jinho-study.tistory.com/1081

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

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

jinho-study.tistory.com

전체 코드는 아래와 같다.

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: //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