[백준][파이썬] 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로 변환하여 입력해주어야 했다. 집합은 직접 수정이 불가능한 자료형인데 리스트는 주소에 의한 수정이 가능해져서가 아닐까 추측해본다.

[백준][파이썬] 15683번 감시

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

Code

import sys


def watch(watched_set, index):              # index : count, cctv 개수 만큼 탐색
    if index == len(cctvs):
        result.append(len(watched_set))
        return
    else:
        for cctv in cctvs[index]:           # cctv[index] 에는 한 cctv의 경우의 수가 모두 저장
            new_s = set(watched_set)
            view(cctv, new_s)               # 각도에 따라서 cctv로 볼 수 있는 위치를 집합에 저장
            watch(new_s, index + 1)


def view(cc, viewd):
    x, y, cctv_type, angle = cc
    d = []
    for idx in range(4):
        d = direction[cctv_type][(idx + angle) % 4] # cctv type과 angle이 정해졌을 때 방향
        if d == 1:
            nx, ny = x + dx[idx], y + dy[idx]
            while -1 < nx < h and -1 < ny < w and office[nx][ny] != 6:
                if office[nx][ny] == 0:     # cctv 있는 위치는 저장 안하도록
                    viewd.add((nx, ny))
                nx = nx + dx[idx]
                ny = ny + dy[idx]


h, w = map(int, input().split())
office = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]

angles = [4, 2, 4, 4, 1]        # type별로 가능한 각도 수
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
direction = [[0, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1], [0, 1, 1, 1,], [1, 1, 1, 1]] # 각도 별로 shift할 리스트

cctvs = []
answer = 0
result = []

for i in range(h):
    for j in range(w):
        if 0< office[i][j] <6:  # cctvs 에 하나의 cctv에서 가능한 각도를 하나의 리스트에 모두 저장
            cctvs.append([[i, j, office[i][j] - 1, angle] for angle in range(angles[office[i][j] - 1])])
        if office[i][j] == 0:   # 0의 개수 세기기
            answer+= 1
watched = set([])

watch(watched, 0)
answer = answer - max(result)   # 0의 개수에서 cctv로 본 위치의 수 빼서 답 구하기
print(answer)

Idea

1. cctv 종류 별로 가능한 각도 수가 다르다.
2. 처음에는 cctv로 본 곳을 #으로 표시했는데 시간이 많이 걸렸다.
3. 입력받은 이차원 리스트를 수정하지 않고 cctv가 본 위치를 저장하는 집합을 만들었다.
4. cctv가 본 위치가 가장 많은 상황에서 0의 개수에서 집합의 길이를 빼면 사각지대를 구할 수 있다.