hibiscus

처음에는 그래프로 만들어서 풀어봤는데, 그래프로 만들다 보니 가지 않는 정점까지 찾아서 다 돌리다보니 시간초과가 났다. 그래서 그냥 큐로 돌리고 방문표시를 통해 되돌아가는 일이 없게 하니 통과했다! 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..

다익스트라로 풀었음! 각자의 집에서 -> 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

처음에는 완전탐색 + 백트래킹을 사용했으나 가지치기가 제대로 안됐는지 시간초과가 떴다. 더 빠른 방법을 고민하다, 제곱근을 찾는 거라 이진탐색을 사용하면 좋을 것 같아 이진탐색을 이용해 풀었다. # 이진탐색으로 해서 시간 단축 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))