문제 미로탐색 해법을 생각해보자. 방법 1: 그냥 떠오르는 대로 bfs로 0,0부터 탐색 가장 먼저 N,M 도착하면 출력하기 n^2 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 from collections import deque directions = [ [0,1], [0,-1], [1,0], [-1,0], ] VISITED = -1 TARGET = '1' queue = deque() queue....
문제 단지 번호 붙이기 주요 로직을 생각해보자. 1번: 막생각 나는 대로 | O(n^3) 2차원 배열을 입력 받는다. 방문 여부를 const로 설정한다. 2차원 배열을 순회한다. 1이 아니면 통과한다. 상하좌우 탐색한다. dfs로 집 수를 찾는다. 집수 list에 저장한다. 집수 list를 정렬한다. 집수를 출력한다. 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 TARGET = '1' VISITED = -1 cost_list = [] directions = [ [0, 1], [0, -1], [1,0], [-1,0] ] def dfs(x,y): global n map_list[x][y] = VISITED localCount = 1 for i in range(4): nx = x + directions[i][0] ny = y + directions[i][1] if nx < 0 or ny < 0 or nx >= n or ny >= n: continue if map_list[nx][ny] !...
핵심 아이디어 NM짜리 이차원 배열을 이용해 최소 치킨 거리를 구한다. 백트랙을 이용해 M개 집 치킨거리를 구한다. 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 n, m = list(map(int, input().split())) city = [] for _ in range(n): city....
생각하기 핵심 로직 브루트포스 i -> i 로 가는지 점검한다. 짝수개여야 가능할 것 같다. 후보군을 리스트로 만든다. 후보군을 백트랙으로 돌면서 3개까지 돈다. 1-3반복한다. 핵심 조건 3보다 크면 -1 불가하면 -1 사고하지 못한점 짝수개여야 가능하다는 것은 필요 조건은 될 수 있어도 충분 조건이 아니다. 다음에 다시풀 문제 핵심 로직 탐지 탐지 하는 방법 내리가면서 시작점과 동일한 끝점인지 확인하기 내리 갈때는 양방향 확인하기 탐색 탐지 nh에 대해서 백트래킹 n^n*h^2 => 90000으로 ㄱㅊ <- 틀림?...
주요 로직 계속 계산하면서 큰값과 작은 값으로 비교한다. 전체 다 돌아야 하며, O(4n)이다. -10억 ~ 10억이므로 int 범위에서 된다. 예상하지 못한 것 음수가 나오는 경우, 나눗셈 연산을 할때 몫을 잘 구해야한다. 음수가 -10억까지 되는데 범위를 잘못 찍었다. code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 n = int(input()) nums = list(map(int, input()....