[백준][파이썬] 17406번 - 배열 돌리기 4

문제 번호 : 17406번 - 배열 돌리기 4
문제 출처 : https://www.acmicpc.net/problem/17406

Code

from itertools import permutations

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
val = []


def matrix_value(ans):
    for i in range(n):
        ans = min(ans, sum(matrix[i]))
    return ans


def rotate(rcs):
    r, c, s = rcs
    for i in range(1, s+1):
        tmp = matrix[r - 1 - i][c - 1 - i]
        x = r - i - 1
        y = c - i - 1
        for j in range(4):
            for k in range(2*i):
                nx = x + dx[j]
                ny = y + dy[j]
                matrix[x][y] = matrix[nx][ny]
                x, y = nx, ny
        matrix[r-1-i][c-i] = tmp


n, m, k = map(int, input().split())
a = [[] for _ in range(n)]
for h in range(n):
    a[h] = list(map(int, input().split()))
rotation = [[] for _ in range(k)]
for i in range(k):
    rotation[i] = list(map(int, input().split()))
answer = 1e9
orders = permutations(rotation)

for order in orders:
    matrix = [a[row][:] for row in range(n)]
    for rcs in order:
        rotate(rcs)
    answer = matrix_value(answer)

print(answer)

Idea

1. 회전하는 경우의 수를 순열을 통해서 구한다. K의 최대값이 6이기 때문에 6! = 720개의 경우가 만들어진다.
2. 각 경우의 수마다 배열을 복사하고 회전을 시킨 후 각 행마다 최솟값인지 확인한다.

[백준][파이썬] 17089 - 세 친구

문제 번호 : 17089번 세 친구
문제 출처 : https://www.acmicpc.net/problem/17089

Code

import sys

n, m = map(int, input().split())
relations = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

friends = [set() for _ in range(n)]
for relation in relations:
    friends[relation[0]-1].add(relation[1])
    friends[relation[1]-1].add(relation[0])

num_friends = m
for a in range(n):
    for b in friends[a]:
        for c in friends[b-1]:
            if c in friends[a]:
                num_friends = min(num_friends, len(friends[a]) + len(friends[b-1]) + len(friends[c-1]) - 6)
if num_friends < m:                
    print(num_friends)
else:
    print(-1)

Idea

1. 입력된 친구가 모두 A, B, C의 친구인 경우 세 친구의 친구 수 합의 최대는 m - 6이다.
2. A를 정하고 B는 A의 친구 중 한명이고 C는 B의 친구이면서 A의 친구인 경우에서 친구 수의 최소값을 찾아낸다.
3. b > a, c > b 조건을 넣은 이유는 먼저 순회한 조합을 순회하지 않기 위함이다. 이 두 조건이 없다면 순열처럼 동작할 것이지만 이 조건으로 인해서 조합이 되어서 시간 복잡도가 줄어든다. 이 조건 두 줄만으로 1880ms에서 92ms로 시간이 확 줄었다.

[백준][파이썬] 2422번 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

문제 번호 : 2422
문제 출처 : https://www.acmicpc.net/problem/2422

Code

import sys

n, m = map(int, input().split())
answer = n * (n - 1) * (n - 2) // 6
nomat = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    answer -= (n-2) - len(nomat[a-1] | nomat[b-1])
    nomat[a-1].add(b)
    nomat[b-1].add(a)

print(answer)

Idea

1. 초기 answer 값은 ${}_n{\mathrm{C}}_3$ 을 수로 나타낸 것이다.
2. nomat 리스트에는 각 맛 별로 조합이 좋지 않은 맛을 넣는다.
3. 2 가지가 정해진 상황에서 나머지 한 가지 맛을 고르는 경우의 수는 n - 2 이다.
4. 그 전에 경우의 수에서 없앤 경우의 수는 합집합의 길이가 된다.

예제 입력을 넣었을 때를 예시로 들면 다음과 같다.

    1. 모든 경우의 수는 5가지 맛 중 3가지를 뽑는 경우로 총 10이다.  
    2. 처음 (1, 2, X) 를 뽑는 경우의 수는 3가지이므로 전체 경우의 수에서 3을 빼준다.  
    3. (3, 4, X) 를 뽑는 경우의 수 중 전에 뽑은 경우가 없으므로 `nomat\[2\]`와 `nomat\[3\]`의 합집합의 길이는 0이다.  
    4. (1, 3, X) 를 뽑는 경우에는 (1, 2, 3) 인 경우와 (1, 3, 4) 인 경우를 그 전의 입력에서 뺐으므로 전체 경우의 수에서 1만 빼준다.

처음에 코드 제출했을 때는 파이썬 언어에서 시간 순위 1등이었는데 글 적을 때 되니까 밀려났다.

[백준][파이썬] 2210번 - 숫자판 점프

문제 번호 : 2210
문제 출처 : https://www.acmicpc.net/problem/2210

Code

import sys


def recursive(x, y, count):
    if count == 5:
        number.append(numbers[x][y])
        answer_set.add(tuple(number))
    else:
        number.append(numbers[x][y])
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx < 5 and -1 < ny < 5:
                recursive(nx, ny, count + 1)
    number.pop()

numbers = [sys.stdin.readline().split() for _ in range(5)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

answer_set = set()
number = []
for r in range(5):
    for c in range(5):
        recursive(r, c, 0)

print(len(answer_set))

Idea

1. 각각의 시작점에서 가능한 방향으로 모두 방문하며 list에 숫자를 추가
2. 숫자 리스트를 집합 자료형에 입력함으로써 중복을 제거
3. 재귀함수가 호출 되고나서 입력받은 리스트와 같은 새로운 리스트를 만들지 않고 기존의 리스트를 append와 pop을 사용해서 스택으로 사용

집합의 요소로는 리스트가 들어갈 수 없다. 그래서 집합에 add를 할 때 리스트를 tuple이나 str로 변환하여 입력해주어야 했다. 집합은 직접 수정이 불가능한 자료형인데 리스트는 주소에 의한 수정이 가능해져서가 아닐까 추측해본다.

[백준][파이썬] 15686번 치킨 배달

문제 번호 : 15686
문제 출처 : https://www.acmicpc.net/problem/15686

Code

import sys
from itertools import combinations

## 입력
n, m = map(int, input().split())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

distance = []   # 집 별로 치킨 집과의 거리 저장
chickens = []   # 치킨 집의 위치와 치킨 집의 번호 저장
houses = []     # 집의 위치 저장
n_chicken = 0
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            houses.append([i, j])
        elif city[i][j] == 2:
            chickens.append([i, j, n_chicken])
            n_chicken += 1

for i in range(len(chickens)):
    distance.append([])
    for house in houses:
        distance[i].append(abs(chickens[i][0] - house[0]) + abs(chickens[i][1] - house[1]))

cases = combinations(chickens, m)

answer = 1e9

for case in cases:
    d = []
    for i in range(m):
        d.append(distance[case[i][2]])

    d = list(map(min, zip(*d)))
    answer = min(sum(d), answer)

print(answer)

Idea

1. N x N 크기의 배열을 모두 탐색하면서 집의 위치와 치킨 집의 위치를 모두 저장
2. 치킨 집의 위치를 저장할 때에는 치킨 집의 number를 차례로 부여
3. 집마다 각 치킨집과의 거리를 저장
4. 치킨 집의 갯수에서 M개의 조합을 생성
5. M개의 조합을 모두 탐색하며 치킨 거리가 최소인 답을 구함

이번 문제에서 zip 함수와 map 함수, 그리고 * 을 사용해서 각 거리들 중 최단 거리를 구했다.
d = list(map(min, zip(*d))) 를 해석해보겠다.
iterable앞에 *을 붙이게 되면 iterable형의 요소들을 모두 반환한다.
예시를 들자면 다음과 같다.

def print_all(a, b, c):
    print(a)
    print(b)
    print(c)

li = [1, 2, 3]
print_all(*li)

### 실행결과
# 1
# 2
# 3

코드에서 d 는 2차원 리스트이므로 여러 개의 1차원 리스트들을 반환한다.
zip함수는 여러개의 iterable이 입력으로 들어오면 index가 같은 요소들끼리 튜플로 합쳐서 반환한다. d의 각 1차원 리스트들은 각 집에서 치킨집들까지의 거리이고 zip함수를 사용하고 나면 각 치킨 집마다의 집들까지의 거리가 된다.
여기에 map함수로 각 리스트별로 min함수를 사용해서 리스트로 반환한다.
처음에 2차원 배열을 모두 돌면서 각 치킨집 별로 최소 거리를 구하는 방법을 사용했고 시간이 400ms가 나왔다. 그런 과정을 저 한 줄의 코드로 변환해서 확인한 결과 112ms로 시간이 많이 줄어들었다.