기본적인 BFS, DFS 문제이다. (N, N) 좌표에 도착할 수 있는지를 확인해주면 된다.
BFS 풀이
from collections import deque
def bfs(y, x):
q = deque()
q.append((y, x, li[y][x]))
while q:
y, x, d = q.popleft()
for i, j in [(1, 0), (0, 1)]:
Y, X = y + d*i, x+ d*j
if 0 <= Y < N and 0 <= X < N and d != 0:
if Y == X == N-1:
return True
q.append((Y, X, li[Y][X]))
return False
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
print("HaruHaru" if bfs(0, 0) else "Hing")
DFS 풀이
import sys
sys.setrecursionlimit(10000)
def dfs(y, x):
global ok
d = li[y][x]
for i, j in [(1, 0), (0, 1)]:
Y, X = y + d*i, x+ d*j
if 0 <= Y < N and 0 <= X < N and d != 0:
if Y == X == N-1:
ok = 1
return ;
dfs(Y, X)
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
ok = 0
dfs(0, 0)
print("HaruHaru" if ok else "Hing")
각 노드별로 몇 명의 사람을 만날 수 있는지 확인하고, 최댓값의 인덱스를 출력해주면 된다 -> res.index(max(res))
def dfs(node, cnt):
check[node] = 1
n = graph[node][0]
if check[n] == 0:
cnt = dfs(n, cnt+1)
return cnt
N = int(input())
graph = [[] for _ in range(N+1)]
res = [0]*(N+1)
for u in range(1, N+1):
v = int(input())
graph[u].append(v)
for i in range(1, N+1):
check = [0]*(N+1)
res[i] = dfs(i, 1)
print(res.index(max(res)))
그 후 아래 내용을 vimrc파일에 입력하고 저장해주면 코드들이 전보다 보기 훨씬 좋아진다!
set number
set ai
set si
set cindent
set shiftwidth=4
set tabstop=4
set ignorecase
set hlsearch
set expandtab
set background=dark
set nocompatible
set fileencodings=utf-8,euc-kr
set bs=indent,eol,start
set history=1000
set ruler
set nobackup
set title
set showmatch
set nowrap
set wmnu
syntax on
여기까지는 직접 설정을 해본 것이고 github를 찾아보니 vimrc 설정 끝판왕이 있는 것 같다.
명령어 두줄이면 바로 적용된다. 만약 git이 안 깔려있다면 sudo apt install git 명령어로 설치해주자.
git clone --depth=1 https://github.com/amix/vimrc.git ~/.vim_runtime
sh ~/.vim_runtime/install_awesome_vimrc.sh
두 단어의 차이가 한 글자면 이동 가능하다. 이동 가능한지 판별하는 부분은 아래의 조건문같이 구현했다.
if len([1 for i in range(N) if node[i] != n[i]]) != 1:
dfs를 사용해서 이동 가능한 모든 경로를 다 돌아보고 현재 node가 target이라면
res리스트에 지나왔던 경로의 길이를 append해준다. 마지막에 min(res)를 반환해주면 끝이다.
def solution(begin, target, words):
def dfs(cnt, node, li, route):
if node == target:
res.append(cnt)
for i, n in enumerate(li):
if len([1 for i in range(N) if node[i] != n[i]]) != 1:
continue
li.pop(i)
dfs(cnt+1, n, li, route+[n])
li.insert(i, n)
if target not in words:
return 0
N = len(begin)
res = []
dfs(0, begin, words, [begin])
return min(res) if res else 0
간단한 그래프 탐색 문제이다. 반복문을 돌면서 체크가 안된 노드가 있다면 ans += 1을 하고
그 노드부터 시작하여 dfs 또는 bfs를 돌려서 갈 수 있는 길을 다 체크해주면 된다.
check[i] = 0 -> i 노드 들린 적 없음 -> 탐색 시작
check[i] = 1 -> i 노드 들린 적 있음 -> 탐색 X
보아하니 백준 실버 4 ~ 실버 2 정도가 프로그래머스 Level 3이랑 비슷한 것 같다.
DFS 풀이
def solution(n, computers):
def dfs(node):
if graph[node] and check[node] == 0:
check[node] = 1
for n in graph[node]:
dfs(n)
graph = [[]]
for i in range(n):
graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
check = [0]*(n+1)
ans = 0
for i in range(1, n+1):
if check[i] == 0:
dfs(i)
ans += 1
return ans
BFS 풀이
from collections import deque
def solution(n, computers):
def bfs(node):
q = deque([node])
while q:
node = q.popleft()
if graph[node] and check[node] == 0:
check[node] = 1
for n in graph[node]:
q.append(n)
graph = [[]]
for i in range(n):
graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
check = [0]*(n+1)
ans = 0
for i in range(1, n+1):
if check[i] == 0:
bfs(i)
ans += 1
return ans
핵심은 dfs 함수를 재귀로 넘기기 전에 딕셔너리의 value값을 삭제하고 재귀후에 다시 추가해주는 부분같다.
처음에 이 부분을 잘못 생각해서 푸는데 오래걸렸다...
from collections import defaultdict
def dfs(N, graph, route, node):
if len(route) == N+1:
return route
for i, n in enumerate(graph[node]):
graph[node].pop(i)
ret = dfs(N, graph, route+[n], n)
graph[node].insert(i, n)
if ret:
return ret
def solution(tickets):
N = len(tickets)
graph = defaultdict(list)
for s, e in tickets:
graph[s].append(e)
for k in graph:
graph[k].sort()
route = dfs(N, graph, ["ICN"], "ICN")
return route
추가로 defaultdict라는 친구에 대해 알게되었다.
여태까지 딕셔너리에 값을 채울 때나 키값이 있는지 조건문으로 확인할 때 get을 사용해서 따로 처리하곤
def solution(n, results):
graph = [[0]*n for i in range(n)]
for a, b in results:
graph[a-1][b-1] = 1
graph[b-1][a-1] = -1
for k in range(n):
for i in range(n):
for j in range(n):
if graph[i][k] == 1 and graph[k][j] == 1:
graph[i][j] = 1
if graph[i][k] == -1 and graph[k][j] == -1:
graph[i][j] = -1
ans = 0
for li in graph:
if li.count(0) == 1:
ans += 1
return ans
from collections import deque
def solution(N, edge):
graph = [[] for _ in range(N+1)]
for a, b in edge:
graph[a].append(b)
graph[b].append(a)
q = deque([1])
check_li = [-1]*(N+1)
check_li[1] = 0
while q:
node = q.popleft()
for n in graph[node]:
if 0 < n <= N and check_li[n] == -1:
q.append(n)
check_li[n] = check_li[node] + 1
ans = check_li.count(max(check_li))
return ans
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()
