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..

SWEA 1795 인수의 생일파티와 유사한 문제이다. 각자의 집 -> 파티하는 집 -> 각자의 집으로 가는 최단경로를 구해야 한다. 한 점에서 여러 점 갈 때는 다익스트라를 한 번 돌리면 되지만, 여러 점에서 한 점으로 갈 때는 각 시작점마다 다익스트라를 돌려야 한다. 불필요하게 다익스트라로 구하는 것을 방지하고자 아예 경로를 여러 점에서 한점으로 가는 것 -> 한 점에서 여러 점을 방문하도록 그래프를 추가했다. 그래서 가는 방향 경로 GO, 오는 방향 경로 COME을 나눠서 다익스트라르 2번 돌려 구했다. from heapq import heappush, heappop INF = 0xffffffffffffffffff # 어떤 시작점에서 모든 정점까지의 최단거리 def dijkstra(start, gra..

dr = [-2, -1, 1, 2, 2, 1, -1, -2] dc = [1, 2, 2, 1, -1, -2, -2, -1] from collections import deque def go(sr, sc): Q = deque() Q.append((sr, sc)) moved = 0 while Q: size = len(Q) for i in range(size): r, c = Q.popleft() if r == er and c == ec: print(moved) return for dir in range(8): nr = r + dr[dir] nc = c + dc[dir] if nr = N or nc >= N or visited[nr][nc]: continue visited[n..

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))