hibiscus

💻 문제 풀이 방법 1. 가능한 경우의 수(조합) 구하기 (재귀 + 백트래킹 사용) 2. 1의 정보를 바탕으로 그룹을 나누고 3. 나눈 그룹 각각 DFS로 방문할 수 있는지 체크, 방문하지 못하는 노드가 있을 경우 제외 처음에는 인접정보를 판단하면서 경우의 수를 구하기 위해, 그래프를 사용하며 방문표시를 했는데, 경우의 수에서 제외되는 경우가 있어 정답을 구할 수 없었다. 경우의 수는 역시 완전 탐색을 하는 게 확실하다... 아래 주소는 문제 풀면서 참고했던 반례들인데 유용했다! https://www.acmicpc.net/board/view/54133 반례들 # DFS def check_areas(check): for i in range(1, N+1): if check[i] == 0: start = i ..

처음에는 BFS로 풀려고 했으나 순간이동은 시간을 세지 않는 다는 점에서 최단 시간을 확정하기 어렵다는 생각이 들었다. 그래서 다익스트라로 접근했다. from collections import deque def find_K(): D = [0xfffffffffff] * 100001 D[N] = 0 Q = deque() Q.append((0, N)) while Q: time, loc = Q.popleft() if D[K] n_loc or 100000 n_time: D[n_loc] = n_time Q.append((n_time, n_loc)) return D[K] N, K = map(int, input().split()) # 수빈, 동생 # 순간이동은 ..

✔ 주의할 점 가능한 경로 2개 1 -> v1 -> v2 -> N 1 -> v2 -> v1 -> N 다익스트라 함수를 만들어 놓고, (1, v1), (v1, v2), (v2, N) (1, v2), (v2, v1), (v1, N) 각 지점 사이의 최단 경로를 구한 뒤, 두가지의 경로 중 최단 거리를 구했다! import sys # 1번 부터 N까지의 최단거리 v1, v2 거쳐서 # 경로없을 때는 1 from heapq import heappop,heappush INF = int(1e9) def dijkstra(start, end): D = [INF] * (N+1) D[start] = 0 Q = [(0, start)] while Q: d, u = heappop(Q) if D[u] < d: continue i..

다른 사람들 풀이 방법 참고해가며 푼 문제...!! 처음에는 DFS로 돌리면 찾을 수 있을 것 같아 DFS로 짰지만, 십자배열 모양은 DFS 특성상 찾아지지 않아 실패했다. 그래서 다른 분들의 접근방법을 참고해봤더니, 1) 5*5 배열의 각 자리수를 카운트해서 이를 인덱스를 활용함을 배웠다. 예를 들어, 왼쪽부터 0, 1, 2, 3, 4 .... 이라고 센다면 1,0은 5가 된다. 그리고 5를 5로 나누면 몫은 1, 나머지는 0 으로 5번째의 행과 열을 구할 수 있게 된다. 새로운 접근 방법이라 생각하지 못했는데, 다른 문제 풀때도 활용할 수 있을 것 같으므로 기억해놓자. 2) 백트래킹할 때 주의하기 코드 논리나 다른 거는 다 맞은 것 같은데 계속 실패가 나왔다. 크게 2가지로 코드를 나눴는데, 25개 ..

3차원 배열을 이용하지 않으면 쉽게 풀리지 않는 문제이다... 처음에는 그냥 2차원 배열에다가, 벽을 부순 여부를 crash 변수로 전달하게끔 했는데.. 잘 되지 않았다. DFS로도 풀어봤는데 DFS는 답은 잘 구해졌는데 시간초과가 났다. 그래서 다른 분들의 풀이를 찾아봤는데 거진 다 3차원배열을 사용해 풀었다. 3차원 배열을 처음 사용해봐서 조금 낯설었는데, 풀어보니 확실히 편하다.. 2차원 배열 + 변수로 하려고 했던 것보다 편하다. 배열을 문제에 맞게 자유자재로 사용하는 것도 능력인 것 같다..! from collections import deque N, M = map(int, input().split()) map = [list(map(int, input())) for _ in range(N)] v..

불을 먼저 퍼뜨리고, 상근이가 bfs 방식으로 이동하게 만들었다. 그래서 불을 퍼뜨리는 fQ, 상근이가 이동하는 Q 이렇게 2개의 Q를 사용해다. 조건에 맞게 사방향으로 잘 이동해주면 쉽게 풀리는 문제였다! 처음에 탈출구에 도착했을 때 함수로 return 하지 않고, 그냥 break를 사용했더니 break 밖의 while문이 있어 예외가 생겼다. from collections import deque delta = [(1, 0), (-1, 0), (0, 1), (0, -1)] #불퍼지기 def fire(): fr, fc = fQ.popleft() if fr - 1 >= 0 and arr[fr - 1][fc] == '.': fQ.append((fr - 1, fc)) arr[fr - 1][fc] = '*' i..

오랜만에 BFS를 인접리스트를 활용해서 푸려니... 기억이 가물가물했다.ㅠ 회장후보를 구하려면 각사람마다 점수를 구하고, 각 사람의 점수들 중 가장 낮은 점수를 가진 사람들을 구해야 한다. 그래서 간선의 시작점(사람)을 바꿔가면 각 시작점(사람)의 점수를 계산했고, 점수가 같을 경우에는 후보군에 추가시켰다. visited 배열을 사용해서 방문체크와 점수 계산을 같이 했다. from collections import deque N = int(input()) graph = [[] for _ in range(N+1)] min_score = 51 candidate = [] while True: person1, person2 = map(int, input().split()) if person1 == -1: bre..

안에 구멍이 있는 경우는 바깥과 연결되어야 녹일 수 있으므로, 핵심은 바깥(외부)을 찾는 것이 중요했다. 그래서 2가지 구조로 나눠 바깥을 체크하고 -> 체크한 바깥과 닿아있는 치즈를 녹이기 -> 다시 바깥을 체크(이때는 녹은치즈 + 새로 생긴 구멍) -> 녹은치즈 이런식으로 체크했다. from collections import deque delta = [(0, 1), (1, 0), (-1, 0), (0, -1)] # 바깥 체크 def outside(): while Q: row, col = Q.popleft() arr[row][col] = -1 for dt in range(4): new_row = row + delta[dt][0] new_col = col + delta[dt][1] if 0

처음에는 완전탐색 + 백트래킹을 사용했으나 가지치기가 제대로 안됐는지 시간초과가 떴다. 더 빠른 방법을 고민하다, 제곱근을 찾는 거라 이진탐색을 사용하면 좋을 것 같아 이진탐색을 이용해 풀었다. # 이진탐색으로 해서 시간 단축 def binary_search(s, e): while True: mid = (s + e)// 2 if (mid ** 2) == N: return mid elif mid ** 2> N: e = mid else: s = mid N = int(input()) print(binary_search(1, N))

처음엔 BFS를 사용하여 A에서 B로 가는 최소횟수를 구했다. 그런데 찾아보니 이런 경우는 B에서 A로 가는 것을 구하면 훨씬 빠르다!! from collections import deque def BFS(): ans = 1 while Q: size = len(Q) for i in range(size): num = Q.popleft() if num > b : continue if num == b: return ans if num * 2 a: ans += 1 if b % 10 == 1: b //= 10 elif b % 2 == 0: b //= 2 else: print(-1) break else: if b < a: print(-1) else: print(ans)