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

처음에는 그래프로 만들어서 풀어봤는데, 그래프로 만들다 보니 가지 않는 정점까지 찾아서 다 돌리다보니 시간초과가 났다. 그래서 그냥 큐로 돌리고 방문표시를 통해 되돌아가는 일이 없게 하니 통과했다! from collections import deque def hamming(): visited[s] = 1 Q = deque() Q.append((s, str(s))) while Q: num, code = Q.popleft() if num == e : return code for i in range(1, N+1): cnt = 0 if visited[i]: continue for j in range(K): if arr[num][j] != arr[i][j]: cnt += 1 if cnt > 1: break if ..

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

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