[python code review] 8주차(병든 나이트, 친구비, 퍼즐)

https://www.acmicpc.net/problem/1783

1783번: 병든 나이트

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://it-college-diary.tistory.com/entry/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-1783%EB%B2%88-%EB%B3%91%EB%93%A0-%EB%82%98%EC%9D%B4%ED%8A%B8

 

 

 

https://www.acmicpc.net/problem/16562

16562번: 친구비

[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번: 퍼즐

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)