728x90
반응형
https://programmers.co.kr/learn/courses/30/lessons/72415?language=python3
코딩테스트 연습 - 카드 짝 맞추기
[[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16
programmers.co.kr
최종 코드
GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음
프로그래머스 알고리즘 소스 코드 모음. Contribute to hwayeon351/Programmers-Algorithms development by creating an account on GitHub.
github.com
from collections import deque
from copy import deepcopy
from itertools import permutations
def bfs(sr, sc, er, ec, board):
dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]
visit = [[0] * 4 for _ in range(4)]
visit[sr][sc] = 1
q = deque([[sr, sc, 0]])
while q:
r, c, cnt = q.popleft()
if r == er and c == ec:
return cnt
for ddr, ddc in zip(dr, dc):
nr = r
nc = c
move = []
for i in range(1, 4):
nr += ddr
nc += ddc
if nr < 0 or nr >= 4 or nc < 0 or nc >= 4:
nr -= ddr
nc -= ddc
move.append([nr, nc])
break
if board[nr][nc] > 0:
move.append([nr, nc])
break
if len(move) > 0:
if visit[move[0][0]][move[0][1]] or (move[0][0] == r and move[0][1] == c): continue
visit[move[0][0]][move[0][1]] = 1
q.append([move[0][0], move[0][1], cnt+1])
else:
if visit[nr][nc]: continue
visit[nr][nc] = 1
q.append([nr, nc, cnt + 1])
for ddr, ddc in zip(dr, dc):
nr = r + ddr
nc = c + ddc
if 0 <= nr < 4 and 0 <= nc < 4:
if visit[nr][nc]: continue
visit[nr][nc] = 1
q.append([nr, nc, cnt + 1])
def solution(board, r, c):
answer = -1
card = [[] for _ in range(7)]
kinds = 0
for y in range(4):
for x in range(4):
if board[y][x] > 0:
card[board[y][x]].append([y, x])
if kinds < board[y][x]: kinds = board[y][x]
idx = [i for i in range(1, kinds+1)]
per = list(permutations(idx, kinds))
for p in per:
nr = r
nc = c
cnt = 0
copy_board = deepcopy(board)
for i in range(len(p)):
choice0 = bfs(nr, nc, card[p[i]][0][0], card[p[i]][0][1], copy_board)
choice1 = bfs(nr, nc, card[p[i]][1][0], card[p[i]][1][1], copy_board)
if choice0 < choice1:
cnt += choice0
cnt += 1
nr = card[p[i]][0][0]
nc = card[p[i]][0][1]
cnt += bfs(nr, nc, card[p[i]][1][0], card[p[i]][1][1], copy_board)
cnt += 1
nr = card[p[i]][1][0]
nc = card[p[i]][1][1]
else:
cnt += choice1
cnt += 1
nr = card[p[i]][1][0]
nc = card[p[i]][1][1]
cnt += bfs(nr, nc, card[p[i]][0][0], card[p[i]][0][1], copy_board)
cnt += 1
nr = card[p[i]][0][0]
nc = card[p[i]][0][1]
copy_board[card[p[i]][0][0]][card[p[i]][0][1]] = 0
copy_board[card[p[i]][1][0]][card[p[i]][1][1]] = 0
if answer == -1 or answer > cnt:
answer = cnt
return answer풀이 과정
from collections import deque
from copy import deepcopy
from itertools import permutations
def bfs(sr, sc, er, ec, board):
#상 좌 하 우
dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]
visit = [[0] * 4 for _ in range(4)]
visit[sr][sc] = 1
#[r, c, 키 조작 횟수]
q = deque([[sr, sc, 0]])
while q:
r, c, cnt = q.popleft()
#목적지에 도착한 경우, cnt 리턴
if r == er and c == ec:
return cnt
#ctrl+방향키 조작
for ddr, ddc in zip(dr, dc):
nr = r
nc = c
move = []
for i in range(1, 4):
nr += ddr
nc += ddc
if nr < 0 or nr >= 4 or nc < 0 or nc >= 4:
nr -= ddr
nc -= ddc
move.append([nr, nc])
break
if board[nr][nc] > 0:
move.append([nr, nc])
break
if len(move) > 0:
if visit[move[0][0]][move[0][1]] or (move[0][0] == r and move[0][1] == c): continue
visit[move[0][0]][move[0][1]] = 1
q.append([move[0][0], move[0][1], cnt+1])
else:
if visit[nr][nc]: continue
visit[nr][nc] = 1
q.append([nr, nc, cnt + 1])
#방향키 조작
for ddr, ddc in zip(dr, dc):
nr = r + ddr
nc = c + ddc
if 0 <= nr < 4 and 0 <= nc < 4:
if visit[nr][nc]: continue
visit[nr][nc] = 1
q.append([nr, nc, cnt + 1])
def solution(board, r, c):
answer = -1
#6 종류의 카드의 위치를 담을 리스트
#card[num] = 카드 종류가 num인 카드들의 위치
card = [[] for _ in range(7)]
#board에 있는 카드 종류
kinds = 0
for y in range(4):
for x in range(4):
#카드가 있는 경우
if board[y][x] > 0:
#해당 카드 종류의 위치를 추가한다
card[board[y][x]].append([y, x])
if kinds < board[y][x]: kinds = board[y][x]
#카드 종류를 담는 리스트
idx = [i for i in range(1, kinds+1)]
#카드 뒤집을 순서 경우의 수 구하기 -> O(kinds!)
per = list(permutations(idx, kinds))
#각 경우의 수에 대하여 카드 짝 맞추기
for p in per:
#현재 커서 위치 초기화
nr = r
nc = c
#조작 횟수 초기화
cnt = 0
#카드 짝 맞추기 시뮬레이션을 위해 board를 카피한다
copy_board = deepcopy(board)
#짝 맞출 카드 종류 순서대로 탐색
for i in range(len(p)):
#해당 카드 종류의 두 카드 중 먼저 뒤집을 카드를 정한다
#현재 위치로부터 가까운 카드를 선택한다
choice0 = bfs(nr, nc, card[p[i]][0][0], card[p[i]][0][1], copy_board)
choice1 = bfs(nr, nc, card[p[i]][1][0], card[p[i]][1][1], copy_board)
#첫번째 카드가 더 가까운 경우, 첫번째 카드를 먼저 탐색한다
if choice0 < choice1:
#1. 첫번째 카드 위치로 이동
#첫번째 카드로 이동하는데 필요한 최소 조작 횟수 카운팅
cnt += choice0
#enter-첫번째 카드 선택
cnt += 1
nr = card[p[i]][0][0]
nc = card[p[i]][0][1]
#2. 두번째 카드 위치로 이동
#두번째 카드로 이동하는데 필요한 최소 조작 횟수 카운팅
cnt += bfs(nr, nc, card[p[i]][1][0], card[p[i]][1][1], copy_board)
#enter-두번째 카드 선택
cnt += 1
nr = card[p[i]][1][0]
nc = card[p[i]][1][1]
#두번째 카드가 더 가까운 경우, 두번째 카드를 먼저 탐색한다
else:
#1. 두번째 카드 위치로 이동
#두번째 카드로 이동하는데 필요한 최소 조작 횟수 카운팅
cnt += choice1
#enter-두번째 카드 선택
cnt += 1
nr = card[p[i]][1][0]
nc = card[p[i]][1][1]
#2. 첫번째 카드 위치로 이동
#첫번째 카드로 이동하는데 필요한 최소 조작 횟수 카운팅
cnt += bfs(nr, nc, card[p[i]][0][0], card[p[i]][0][1], copy_board)
#enter-첫번째 카드 선택
cnt += 1
nr = card[p[i]][0][0]
nc = card[p[i]][0][1]
#짝 맞춘 카드 없애기
copy_board[card[p[i]][0][0]][card[p[i]][0][1]] = 0
copy_board[card[p[i]][1][0]][card[p[i]][1][1]] = 0
#최소 조작 횟수 갱신
if answer == -1 or answer > cnt:
answer = cnt
return answer
728x90
반응형
'코테 노트 > 프로그래머스' 카테고리의 다른 글
| Level 3 양과 늑대 <2022 KAKAO BLIND RECRUITMENT> Python 3 (0) | 2022.05.06 |
|---|---|
| Level 3 파괴되지 않은 건물 <2022 KAKAO BLIND RECRUITMENT> Python 3 (0) | 2022.05.06 |
| Level 3 광고 삽입 <2021 KAKAO BLIND RECRUITMENT> Python 3 (0) | 2022.05.05 |
| Level 3 외벽 점검 <2020 KAKAO BLIND RECRUITMENT> Python 3 (0) | 2022.04.07 |
| Level 3 기둥과 보 설치 <2020 KAKAO BLIND RECRUITMENT> Python 3 (0) | 2022.04.02 |