codeollie

문제 해석 우선 태그를 BFS로 검색해서 찾은 문제이지만 BFS로 풀었을때 cnt를 어떻게 셀지를 고민하다가 B를 A로 만드는 규칙이 눈에 보여서 그리디 알고리즘으로 풀었는데 그리디 알고리즘으로도 풀 수 있는 문제였다. 문제 풀이 그리디 import sys A, B = map(int, sys.stdin.readline().split()) def solution(A, B): cnt = 1 while B != A: if B % 10 == 1: B = int(B / 10) else: B = int(B / 2) cnt += 1 if A == B: return cnt else: return -1 print(solution(A, B)) 처음 풀었던 풀이인데 47%에서 틀린 풀이이다. 우선 틀린 이유는 위에 나온 조..

문제 해석 간선과 정점으로 입력을 받지만 인접한 노드의 탐색의 이루어지는 구역의 수를 구하는 기존 문제와 풀이 방식은 똑같다. 문제 풀이 import sys from collections import deque N, M = map(int, sys.stdin.readline().split()) graph = [[] for _ in range(N + 1)] visited = [False for _ in range(N + 1)] for _ in range(M): v1, v2 = map(int, sys.stdin.readline().split()) graph[v1].append(v2) graph[v2].append(v1) result = 0 def BFS(x): deq = deque() deq.append(x)..

문제 해석 대각선을 포함해서 인접한 노드를 찾는 탐색문제였다. 대각선까지 탐색하는 문제는 처음이였지만 어차피 대각선 인덱스만 추가로 탐색을 해주면 되는 것이기 때문에 풀이 자체는 어렵지 않았다. 문제 풀이 import sys from collections import deque def BFS(x, y): dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] deq = deque() deq.append((x, y)) graph[x][y] = 0 while deq: x, y = deq.popleft() for i in range(8): nx = x + dx[i] ny = y + dy[i] if nx = H or ny < 0 ..

문제 해석 두 사람의 촌수를 구한다는 의미는 입력받은 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 탐색 시작 노드와 탐색 종료 노드를 뜻하는 것이라고 볼 수 있다. 문제 풀이 import sys from collections import deque N = int(sys.stdin.readline().rstrip()) x, y = map(int, sys.stdin.readline().split()) M = int(sys.stdin.readline().rstrip()) graph = [[] for _ in range(N + 1)] visited = [0 for _ in range(N + 1)] for _ in range(M): v1, v2 = map(int, sys.stdin.readline().spl..

문제 해석 이문제도 이전에 풀어본 문제와 마찬가지로 탐색을 진행한 구역의 수를 구하는 문제이다. 하지만 다른점이 있다면 1인 좌표를 입력받고 보드판을 직접 만들어야 하는 것이였다. 문제 풀이 def BFS(x, y): deq = deque() deq.append((x, y)) graph[x][y] = 0 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] while deq: x, y = deq.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx = N or ny = M: continue if graph[nx][ny] == 1: graph[nx][ny] = 0 deq.append((nx,..

문제 해석 이전에 풀어본 예제와 같은 기본적인 BFS를 이용한 최단경로 문제이다. 문제 풀이 import sys from collections import deque def BFS(x, y): deq = deque() deq.append((x, y)) while deq: x, y = deq.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if nx = N or ny = M: continue else: if graph[nx][ny] == 1: graph[nx][ny] = graph[x][y] + 1 deq.append((nx, ny)) return graph[N - 1][M - 1] N, M = map(int,..

문제 해석 BFS나 DFS를 이용해서 1인 구역의 갯수와 해당 구역의 1의 수를 구하는 문제이다. 이 문제는 저번에 DFS/BFS를 정리하면서 풀었던 예제 아이스크림 얼려 먹기 문제와 미로 탈출 문제를 합친 것 같았다. 그래서 처음엔 그 두 문제의 풀이법을 그대로 섞어서 사용하면 답이 나올 것으로 생각했다. 문제 풀이 두 풀이법의 혼용이라 함은 for i in range(N): for j in range(N): if graph[i][j] == 1: apart.append(BFS(i, j)) 함수의 호출부분이 모든 그래프의 노드를 훑으면서 탐색을 시작할 수 있는 노드를 찾는 방식으로 탐색이 이루어진 구역의 수를 찾는 아이스크림 얼려 먹기 문제의 방식과 if graph[nx][ny] == 0: continu..

문제 해석 루트 노드가 없는 트리가 있는데 트리의 루트를 1이라고 가정했을때, 각 노드의 부모를 구한다는 상황이다. BFS나 DFS를 이용해서 탐색을 했을때 해당 노드가 방문처리되기 이전의 노드가 부모노드라고 추측했다. 문제 풀이 import sys from collections import deque N = int(sys.stdin.readline().rstrip()) graph = [[] for _ in range(N + 1)] for _ in range(N - 1): v1, v2 = map(int, sys.stdin.readline().split()) graph[v1].append(v2) graph[v2].append(v1) visited = [0 for _ in range(N + 1)] deq =..

문제 해석 이 문제는 1을 시작노드로 하여 방문할 수 있는 노드의 수를 모두 구하는 탐색 문제이다. 문제 풀이 DFS나 BFS를 구현할 수 있다면 별다른 문제없이 그 자체로 해결되는 문제이며 BFS를 이용해서 풀었다. import sys from collections import deque N = int(sys.stdin.readline().rstrip()) M = int(sys.stdin.readline().rstrip()) graph = [[] for _ in range(N + 1)] for _ in range(M): v1, v2 = map(int, sys.stdin.readline().split()) graph[v1].append(v2) graph[v2].append(v1) cnt = 0 visit..

DFS(Depth First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조 혹은 재귀 함수를 이용하며, 동작과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더이상 2번의 과정을 수행할 수 없을때까지 반복한다. 위와 같은 그래프에서 시작노드 1부터 깊이 우선 탐색을 진행한다면 과정은 다음과 같다. def DFS(graph, x, visited): stk = [] stk.append(x) visited[x] = True while ..