https://www.acmicpc.net/problem/1325 [초기 접근 방법] - '한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호' 출력 - 각 노드, 즉 각 컴퓨터에서 bfs 탐색을 하며 그 깊이를 측정하고 가장 깊은 노드를 출력하면 오름차순으로 출력한다. [생각] - 단순한 그래프 탐색 문제 [코드] # 풀이 시간 : 15분 # 시간복잡도 : O(N+e) # 공간복잡도 : O(N+e) # 참고 : - # Python3는 시간초과 from collections import deque def bfs(k): visited = [False] * (N + 1) # 계속 초기화 필요 cnt = 0 # 연결된 간선 갯수 세기 q = deque() q.append(k) visited[k] = Tr..

https://www.acmicpc.net/problem/1600 [초기 접근 방법(x)] 1. 일단 도보로만 이동한다고 생각하고, 목적지까지의 이동횟수를 구한다. (bfs) 2. 목적지에서 K번 '말'의 방향으로 뛰어본다. (dfs) - visited[][] 값이 있을 경우, 즉 도보로 갈 수 있는 경우 result 값을 갱신한다. [생각] 위의 접근이 틀린 이유는, 중간에 '말' 동작을 실행할 수도 있다는 것이다. 저 방법대로라면, 끝에서밖에 '말' 동작을 실행한다. 아예 틀린 접근으로 시간을 소비하고, 블로그를 참조하여 다시 풀이했다. 아.. 그리고 python에서 3차원 배열을 정의하는데, 개념을 잡느라 시간을 많이 썼다. lst = [[[0 for _ in range(depth)] for _ i..

[초기 접근 방법] 1. 정육각형이므로, 6개의 지역에 접근해야 한다. - 짝수 행, 홀수 행에 따라 육각형의 탐색 범위가 달라진다. 2. 그런데 닫힌 구역을 어떻게 판단하지? - 이 부분에 대해서 visited[i][j] == 6 일 경우로 판단하자 라고 생각했지만, 닫힌 구역내의 육각형이 여러 개일 경우 불가한다.. [생각] 예전에 팀프로젝트로 미로찾기 알고리즘을 한 적이 있었는데, 기능 중 하나로 '닫힌 구역에 대해서 미로가 더 이상 탐색하지 않게끔 한다.' 가 떠올랐다. 각설하고, 생각을 해보았지만 닫힌 구역에 대한 판단에 대한 알고리즘이 떠오르지 않아 블로그를 참조했다. 1. 한 번에 바깥쪽의 공간 지역 전체 탐색하기 위해, 상하좌우 4개의 구역을 1칸씩 늘려준다. 2. 주변 6개의 인접 구역..

[초기 접근 방법] 1초 - 초기 상태 2초 - 폭탄이 설치되어 있지 않은 모든 칸 폭탄 설치 3초 - '초기 폭탄'의 인접 지역 펑! 4초 - 폭탄이 설치되어 있지 않은 모든 칸 폭탄 설치 5초 - 2초에 설치된 폭탄 펑! 6초 - 폭탄이 설치되어 있지 않은 모든 칸 폭탄 설치 7초 - 4초에 설치된 폭탄 펑! [생각] 홀수∙짝수 시간에 대한 규칙을 찾고, 폭탄을 구분해서 어떻게 터트릴까 고민했던 문제 왜 이렇게 오래 걸렸을까? → 머리로만 생각하지말고, 직접 메모로 기록하면서 반복되는 규칙을 찾자 [코드] # 풀이 시간 : 1시간 30분 # 시간복잡도 : O((N/2) * (5B + RC)) # N회 반복 # 홀수 : bfs 폭탄 터지기 (5개 간선, 폭탄 개수 B) # 짝수 : 모든 칸 폭탄 설치..

https://www.acmicpc.net/problem/2412 [초기 접근 방법]1. (0, 0)에서 조건에 만족하는 홈을 찾아 큐에 넣는다.2. bfs를 돌려가며, 각 홈에서 조건에 만족하는 홈을 찾는다. + (x, y, dis)    조건 설정에서 틀렸다. ( ' )3. dis 값이 더 작은 것으로 유지한다.4. y좌표가 T일 때 함수를 종료한다. [생각]1. O(25억)인데 시간초과가 나지 않나..     역시 시간초과가 났고, set()을 활용해서 dot(홈)에 접근하는 속도를 높이려 했다.2. 이 역시도 시간초과.. dot(홈)을 전부 접근하려는 게 문제였다.     현재 위치를 중심으로, 범위 설정을 함으로써(lower_bound) 푸는 문제였다.3. queue의 pop 개념을 사용하려면,..