본문 바로가기

전체 글92

[python] 15683. 감시 문제 출처 15683. 감시 풀이 DFS deepcopy (0% 시간초과) from copy import deepcopy N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] cameras = [[] for _ in range(5)] for y in range(N): for x in range(M): if 0 < arr[y][x] < 6: cameras[arr[y][x]-1].append((y, x)) c1_w = [[1], [2], [3], [4]] c2_w = [[1, 3], [2, 4]] c3_w = [[1, 2], [2, 3], [3, 4], [4, 1]] c4_w = [[1, 2, 3],.. 2019. 7. 24.
[python] 14890. 경사로 문제 출처 14890. 경사로 풀이 N, L = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] def check(lst): i = 0 stack = 1 now = lst[i] while i 1 or diff N: return False for j in range(i+1, i+L): if now - lst[j] != 1: return False stack = 1-L elif diff == -1: if i-L < 0 or stack < L: retur.. 2019. 7. 15.
[python] 14503. 로봇 청소기 문제 출처 14503. 로봇 청소기 풀이 로봇이 바라보고 있는 위치에서 청소하기위해 이동할때 좌표의 변화량과 바라보는 방향을 표시하는 방향 딕셔너리를 만든다. 로봇이 네 방향 모두 청소하지 못할때 후진하기 위한 좌표의 변화량을 방향별로 표시하는 후진 딕셔너리를 만든다. 이동 횟수를 1로 초기화한다. 현재 로봇의 좌표에 해당하는 배열의 값을 바꿔 청소가 완료된 것을 표시한다. 방향 딕셔너리에서 해당 방향의 배열을 순회하며 청소 가능 유무를 확인한다. 청소가 가능하면 이동 횟수를 증가시키고 다음 위치로 이동하고 4번으로 돌아간다. 청소가 불가능 하면 후진 딕셔너리에서 다음 위치를 찾아 이동하고 4번으로 돌아간다. 청소가 불가능 하고 후진 했을때 배열 범위를 벗어나거나 벽이면 작업을 완료한다. N, M = m.. 2019. 7. 15.
[python] 14502. 연구소 문제 출처 14502. 연구소 풀이 초기에 주어진 배열에서 벽이 더이상 추가되지 않는다면 BFS탐색을 통해 바이러스를 퍼뜨린 후, 더이상 바이러스가 퍼지지 않을 때의 빈공간의 갯수를 구하면 된다. 하지만 이 문제는 3개의 벽을 추가로 세워야 하기 때문에 초기 배열에서 빈 공간의 좌표를 파악하고 좌표들 중 3개를 뽑는 조합을 계산한 후 바이러스를 퍼뜨려 안전 영역 크기의 최댓값을 구하면 된다. 초기 배열에서 바이러스와 빈 공간의 좌표들을 저장한다. 벽을 추가로 3개 세웠다고 가정했을때의 빈 공간의 갯수를 구하고, 최댓값을 초기화 한다. 빈 공간의 좌표를 기록한 리스트에서 중복되지 않는 3개의 좌표를 뽑는다. 3번에서 구한 조합의 모든 경우에서 같은 작업을 반복해야 하므로 초기의 배열과 바이러스를 저장한 리.. 2019. 7. 13.

티스토리툴바