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

다익스트라로 풀었음! 각자의 집에서 -> X번 집(생일파티집) => 각자의 집 X번 -> 각자의 집은 다익스트라 한 번 돌리면 되지만, 각자의 집에서 X번집의 최단거리들을 구하려면 여러번 돌아야 한다. 그래서 그래프를 만들때 각자의 집 -> X번 집을 쉽게 구하기 위해서 X 번집을 기준으로 두고, 각자의 집으로 가는 (반대방향) 으로 그래프를 만들어 다익스트를 2번만 돌리면 되도록 했다! from collections import deque INF = int(1e9) def dijkstra(start, graph): D = [INF] * (n + 1) D[start] = 0 Q = deque() Q.append(start) while Q: node = Q.popleft() for n_node, w in ..

N-queen 문제 처음에 N-Queen 문제를 봤을 땐 어떻게 접근해야할 지 몰랐고, 이해가 가는 풀이가 없었다. 그런데 아래 풀이를 통해 이해에 도움을 받아 정리해둔다!! 첫번째는 가로, 세로(i, cols) + 대각선(diagonal) 을 검사했다. 대각선의 경우에는 이전에 입력된 좌표의 값과 입력할 좌표의 값의 차이가 똑같다는 것을 이용해 푸는 것이다. 두번째는 4 * 4 배열일 경우, row와 col을 더하면 아래와 같이 나타나진다. 이런 경우, 대각선끼리 숫자가 같게 되므로 동일한 숫자를 가진 좌표들이 동일 대각선에 위치함을 이용해 푸는 것이다!! 0 1 2 3 1 2 3 4 2 3 4 5 3 4 5 6 하지만, 위의 경우는 오른쪽 대각선만 알 수 있으므로 왼쪽 대각선도 따로 구해야 한다. 왼..

다른 사람들 풀이 방법 참고해가며 푼 문제...!! 처음에는 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