무럭무럭 자라라

[Silver I] 데스 나이트 - 16948 문제 링크 성능 요약 메모리: 32452 KB, 시간: 108 ms 분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다. 데스 나이트..

[Silver I] 돌다리 - 12761 문제 링크 성능 요약 메모리: 33496 KB, 시간: 292 ms 분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 동규와 주미는 일직선 상의 돌 다리 위에있다. 돌의 번호는 0 부터 100,000 까지 존재하고 동규는 N\(N\)번 돌 위에, 주미는 M\(M\)번 돌 위에 위치하고 있다. 동규는 주미가 너무 보고싶기 때문에 최대한 빨리 주미에게 가기 위해 A,B\(A, B\) 만큼의 힘을 가진 스카이 콩콩을 가져왔다. 동규가 정한 다리를 건너는 규칙은 턴 방식인데, 한 턴에 이동할 수 있는 거리는 이러하다. 현 위치에서 +1칸, -1칸을 이동할 수 있고, 스카이 콩콩을 이용해 현 위치에서 A\(A..

[Silver I] 영역 구하기 - 2583 문제 링크 성능 요약 메모리: 32440 KB, 시간: 104 ms 분류 너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 ..

[Silver I] 안전 영역 - 2468 문제 링크 성능 요약 메모리: 32484 KB, 시간: 1448 ms 분류 너비 우선 탐색(bfs), 브루트포스 알고리즘(bruteforcing), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 ..

""" *packageName : * fileName : 1926_그림_S1 * author : ipeac * date : 2022-06-16 * description : * =========================================================== * DATE AUTHOR NOTE * ----------------------------------------------------------- * 2022-06-16 ipeac 최초 생성 """ from collections import deque dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] cnt = 0 def bfs(graph, visited, x, y): width = 1 global cnt vi..

""" *packageName : * fileName : 1389_케인베이컨의6단계법칙_S1 * author : ipeac * date : 2022-06-15 * description : * =========================================================== * DATE AUTHOR NOTE * ----------------------------------------------------------- * 2022-06-15 ipeac 최초 생성 """ from collections import deque def bfs(node_list, R): visited = [0] * (N + 1) q = deque() q.append(R) visited[R] = 1 while..

""" *packageName : * fileName : 5567_결혼식_S2 * author : ipeac * date : 2022-06-12 * description : * =========================================================== * DATE AUTHOR NOTE * ----------------------------------------------------------- * 2022-06-12 ipeac 최초 생성 """ def dfs(graph, visited, R, depth): # 친구의 친구까지만 구해야합니다. 0 (친구) 1 (친구의 친구) if depth >= 2: return print("graph : %s " % graph) for i..

import sys sys.setrecursionlimit(100000) def dfs(graph, v, visited, nodes_cnt): global cnt # 방문처리 visited[v] = True # 노드 방문 순서 기록 nodes_cnt[v] = cnt cnt += 1 # 연결된 노드로 이동할 수 있도록 ! for i in graph[v]: if not visited[i]: dfs(graph, i, visited, nodes_cnt) N, M, R = (map(int, input().split())) # 그래프 graph = [[] for _ in range(N + 1)] visited = [False for _ in range(N + 1)] nodes_cnt = [0 for _ in ran..