[python code review] 8주차(병든 나이트, 친구비, 퍼즐)
https://www.acmicpc.net/problem/1783
1783번: 병든 나이트
첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
n, m = map(int, input().split())
if n == 1:
print(1)
elif n == 2:
print(min(4, (m+1)//2))
else:
if m < 7:
print(min(4, m))
else:
print(m-2)힌트) 행을 기준으로 조건을 나눈다.
ex. 행이 1일때, 2일때, 2 이상일때...
코드는 간단하나 이해하는데 어려움이 많았던 풀이
n = 1인 경우
이런 상태이기 때문에 나이트는 어느 방향으로도 움직이지 못한다.현재 위치만을 포함한 1 출력
n = 2인 경우
문제에서의 조건) 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다.
즉, 나이트의 이동 횟수가 4번 이상이라면 4가지 방법을 모두 사용해야 한다. 하지만
이 케이스의 경우 위와 같은 방향으로 움직이지 못하기 때문에 최대 3번만 이동 가능하다.따라서 나이트가 방문할 수 있는 최대 칸수는 3 + 1(현재 위치) = 4 이다.이때, 열에 따라서 나이트가 방문할 수 있는 칸수는 (m + 1) // 2 와 같은 공식을 갖는다.
열(m)이 2이라면 (2+1) // 2 = 1 나이트가 방문할 수 있는 칸 수
열(m)이 3이라면 (3+1) // 2 = 2 나이트가 방문할 수 있는 칸 수
열(m)이 4이라면 (4+1) // 2 = 2 나이트가 방문할 수 있는 칸 수
따라서 나이트가 방문할 수 있는 칸 수는 min(4, (m+1)//2)
n >= 2인 경우
열(m)이 7보다 크거나 같다면
주어진 방향대로 각각 1번씩은 이동이 가능하다.
이때 나이트가 최대한 많이 방문하기 위해서는 오른쪽으로 2칸씩 이동하는 방향을 단 2번만 사용하고
1번만 오른쪽으로 이동하는 방향인
얘네를 최대한 많이 사용해야 한다.
이때 나이트가 방문 가능한 최대 칸 수는 m - 2 (오른쪽으로 2칸씩 이동하는 방향 1씩 제거)
열(m)이 7보다 작다면
네가지 방향으로 이동할 수 없다.
행이 2이상인 경우, 위 아래로 2칸씩 이동할 수 있다.
따라서 오른쪽으로 한칸 씩만 이동한다면 나이트는 최대로 방문할 수 있다. (그리디)
이때 이동 가능한 횟수는 m-1 개이다. 하지만 이 컨셉을 유지한다면 m-1은 최대 3을 넘기지 못한다.
(이동 가능한 횟수가 4일 경우 모든 방향으로 이동해줘야하므로)
참고한 블로그)
https://velog.io/@dding_ji/baekjoon-1783
https://www.acmicpc.net/problem/16562
16562번: 친구비
첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (
www.acmicpc.net
[bfs 사용]
from collections import deque
n, m, k = map(int, input().split())
cost = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
def bfs(x):
global visited
deq = deque([x])
visited[x] = True
result = cost[x]
while deq:
now = deq.popleft()
for next_node in graph[now]:
if not visited[next_node]:
visited[next_node] = True
result = min(result, cost[next_node])
deq.append(next_node)
return result
answer = 0
for i in range(1, n+1):
if not visited[i]:
answer += bfs(i)
# 모든 친구에게 방문하지 못한 경우
for i in range(1, n+1):
if not visited[i]:
print('Oh no')
exit()
# 현재 가진 돈이 부족한 경우
if answer > k:
print('Oh no')
else:
print(answer)주어진 input 값이 모든 친구를 만날 수 있다는 보장이 없어서
# 모든 친구에게 방문하지 못한 경우
for i in range(1, n+1):
if not visited[i]:
print('oh no')
exit()
위와 같은 코드를 추가하였는데 제거해도 상관없었다..
[코드 개선]
from collections import deque
n, m, k = map(int, input().split())
cost = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
def bfs(x):
global visited
deq = deque([x])
visited[x] = True
result = cost[x]
while deq:
now = deq.popleft()
for next_node in graph[now]:
if not visited[next_node]:
visited[next_node] = True
result = min(result, cost[next_node])
deq.append(next_node)
return result
answer = 0
for i in range(1, n+1):
if not visited[i]:
answer += bfs(i)
# 현재 가진 돈이 부족한 경우
if answer > k:
print('Oh no')
else:
print(answer)
https://www.acmicpc.net/problem/1525
1525번: 퍼즐
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.
www.acmicpc.net
from collections import deque
def bfs(start):
global board
deq = deque([start])
move = [(1,0),(0,1),(-1,0),(0,-1)]
board[start] = 0
while deq:
now = deq.popleft()
if now == '123456780':
return board[now]
# 문자열에서 '0'의 위치
loc = now.find('0')
# '0'의 좌표
x, y = loc // 3, loc % 3
for dx, dy in move:
nx = x + dx
ny = y + dy
if not(0 <= nx < 3 and 0 <= ny < 3):
continue
# 문자열에서 타켓 숫자의 위치
n_loc = nx * 3 + ny
swapLst = list(now)
swapLst[n_loc], swapLst[loc] = swapLst[loc], swapLst[n_loc]
nxt = ''.join(swapLst)
if not board.get(nxt, 0):
board[nxt] = board[now] + 1
deq.append(nxt)
return -1
# 문자열 : 해당 문자열에 도달하기까지의 최소 이동 횟수
board = {}
s = ''
for _ in range(3):
s += ''.join(input().split())
print(bfs(s))하도 안풀려서 처음엔 bfs로 접근한다는 힌트를 가지고 풀어봤는데 방문처리를 어떻게 해야할지 도무지 생각나지 않았다.
알고보니 딕셔너리를 활용하여 최소방문 횟수를 구할 수 있는 문제였다.
# '0'의 좌표
x, y = loc // 3, loc % 3
# 문자열에서 타켓 숫자의 위치
n_loc = nx * 3 + ny
이런 아이디어는 전혀 생각치 못해서 잘 기억해두면 좋을 것 같다.
[틀린 풀이]
두 테스트 케이스에 대해서는 통과했지만 이런 식으로 풀면 안되는 이유는
visited로 방문 처리를 한다면 숫자들이 아무리 이동해봤자 총 9번 밖에 이동하질 못한다.즉, 한 번 방문했던 위치더라도 다시 방문할 수 있도록 방문 처리 로직을 만드는 게 이 문제의 핵심이다. 따라서 문자들의 위치를 아예 하나의 문자열로 저장하는 방식 (board 딕셔너리)으로 최소 방문 횟수를 구할 수 있다.
from collections import deque
target = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
board = [list(map(int, input().split())) for _ in range(3)]
visited = [[False]*3 for _ in range(3)]
move = [(1,0), (0,1), (-1,0), (0,-1)]
# print(board)
# 같은 상태인지 검사
def check():
for i in range(3):
for j in range(3):
if board[i][j] != target[i][j]:
return False
return True
def bfs(x, y):
global count
deq = deque([(x, y)])
while deq:
x, y = deq.popleft()
for dx, dy in move:
nx = x + dx
ny = y + dy
if 0 <= nx < 3 and 0 <= ny < 3:
# 옮겨도 되는 좌표라면
if not visited[nx][ny]:
board[nx][ny], board[x][y] = board[x][y], board[nx][ny]
visited[x][y] = True
count += 1
deq.append((nx, ny))
# 이동할 필요가 없는 좌표는 방문 처리
for i in range(3):
for j in range(3):
if target[i][j] == board[i][j]:
visited[i][j] = True
count = 0
for i in range(3):
for j in range(3):
# 비어있는 좌표라면
if board[i][j] == 0:
bfs(i, j)
if check():
print(count)
else:
print(-1)