아이테킨의 끄적끄적

DFS알고리즘을 알고 있어야 풀 수 있는 문제다. R,C로 행과 열의 값 pipe에 파이프라인 visited에 파이프가 이미 설치되어 있는 곳인지 확인하기 위해 False로 초기화 리스트 이런 변수들을 입력 및 선언하고 왼쪽부터 시작해서 맨 오른쪽이 원웅이네 가게 파이프라인까지 최대한 많은 선을 연결해야 하므로 첫번째 열 에서 파이프라인이 있는 지점 pipe[i][0] == '.' 에서 부터 탐색을 시작한다. solve함수를 호출하여 건물이 있는 지점을 피하며 오른쪽으로 이동하고, 방문했던 지점은 True로 흔적을 남긴다. solve함수 종료조건인 j == C - 1 까지 도착하게 되면 True를 반환하여 cnt를 증가시킨다. # 3109번 : 빵집 def solve(i,j): # 원웅이네 파이프로 무사..

기본적인 탐색문제로 DFS,BFS알고리즘중 하나를 선택해서 풀면 된다. 나는 DFS를 이용해서 풀었고 DFS알고리즘은 재귀함수를 사용하기 때문에 미리 재귀깊이를 늘려놓는것이 편하다. dfs함수를 만들어주고 check라는 리스트에 계속해서 숫자를 더하는 방법으로 촌수를 계산해보았다. # 2644번: 촌수계산 import sys sys.setrecursionlimit(10*5) def dfs(node): for n in graph[node]: if check[n] == 0: check[n] = check[node]+1 dfs(n) n = int(input()) graph = [[] for _ in range(n+1)] s,e = map(int,input().split()) for _ in range(int(..

이 문제는 루트노드가 1로 가정하고 있으므로 2번부터 n-1번까지 순서대로 노드들의 부모노드를 찾아서 출력해주면 되는 문제이다. 탐색문제이므로 dfs,bfs 등 편한 알고리즘을 사용하면 될 것 같다. 나는 dfs알고리즘을 이용해서 풀어보았다. 우선 dfs알고리즘을 사용할 때는 재귀의 깊이를 늘려놓는 것이 편하다. 그리고 트리구조를 표현할 때 인접리스트(adjacent list)방식으로 표현했다. 인접리스트만으로는 부모와 자식노드의 관계를 알 수는 없다. 따라서 parent리스트를 따로 만들어서 순서대로 부모노드를 넣어주었다. # 11725번: 트리의 부모 찾기 import sys sys.setrecursionlimit(10**6) n = int(input()) adj_list = [[] for _ in ..

dfs방법으로 풀어보았다. 이번 문제에서는 print(*list)에 대해서 알 수 있게 되었다. 원래는 for 루프를 이용해서 sep연산자와 함께 사용해서 리스트를 출력했었는데 블로그를 통해서 리스트를 파이썬 *연산자와 함께 출력하면 깔끔하게 보기좋게 출력된다. 더 알아보고 싶으신 분들은 https://www.askpython.com/python/list/print-a-python-list https://www.daleseo.com/python-lists-print/ 위의 링크들 참조하면 좋을것 같다. import sys sys.setrecursionlimit(10000) m,n,k = map(int,input().split()) # 1. 그림그리기 graph = [[0]*n for i in range(..

dfs로 탐색문제이다. dfs는 재귀,스텍 자료구조를 이용하는 알고리즘인데 어짜피 같은 원리이지만 나는 주로 재귀를 사용해서 문제를 푼다. dfs알고리즘은 문제를 반복적으로 풀어보게 되면 익숙해질것이고 이 문제는 적록색약(녹색과 빨간색을 구분 못하는 사람)을 신경써서 풀어줘야 하는데 나는 그냥 graph를 딥카피 한후에 R를 G로 바꿔버렸다. 반복문을 많이 쓰게 되서 시간초과가 날까 걱정이 되기도 했는데 일단 통과는 되었다. :) import copy import sys sys.setrecursionlimit(100000) n = int(input()) graph = [] for _ in range(n): i = list(map(str,input())) graph.append(i) graph2 = cop..

기본적인 탐색문제인 듯 하다. 이 문제는 DFS로 풀 수 있는데 푸는 방법을 굳이 나눠보자면 인접행렬과 인접리스트 방식으로 풀 수 있다. 이 차이는 그래프를 표현하는 방식의 차이일뿐 본질적인 차이는 없다. 표현 방식에 따라서 코딩을 해주면 된다. 나는 인접행렬 형식으로 풀어보았다. 인접리스트 방식으로 푼 풀이가 궁금하신 분들은 https://hjp845.tistory.com/33 여기 블로그에 코드가 있으니 참고하면 된다. 그러나 알고리즘이 아닌 다른 부분에서 좀 해맸다. 1. sys.setrecursionlimit(10000) 재귀를 사용할 땐 항상 재귀의 깊이를 넉넉하게 설정해주는 것을 잊지 말아야 한다. 이걸 안해주면 런타임에러(recursuionerror)가 뜬다. 2. sys.stdin.read..

bfs문제다. 최단거리를 찾는 문제는 bfs탐색법을 활용하면 된다. bfs는 큐 자료구조를 활용하는데 큐에서 한개씩 꺼내서 연결된 노드들을 탐색하면서 큐가 빌때까지 루프를 돌려주면 되는 탐색 알고리즘이다. # 2178 미로 탐색 - 최단거리 n,m = map(int,input().split()) graph = [] for _ in range(n): graph.append(list(map(int,input()))) arrow = [[-1,0],[1,0],[0,-1],[0,1]] # 상하좌우 from collections import deque def bfs(x,y,step=1): q = deque() q.append([x,y]) while q: node = q.popleft() for i in arrow:..

이번 문제는 이전 단지번호 붙이기(2667번)에서 사용되었던 방법을 이용하면 풀수 있다. 아니, 문제 자체는 오히려 더 쉽다. 하지만 이번 문제에서도 에러를 만나게 되었는데 바로 런타임에러(recursion error)이다. 이놈을 만나고 나서 계속 코드를 하나하나 뜯어보았다. 분명히 코드엔 잘못된 부분이 없는것 같다. base case조건도 분명하게 걸어놨고 테스트 입력값에서도 잘 돌아갔다. 구글링을 통해서 찾아보니 재귀의 깊이제한을 설정해줘야 한다는 것을 알았다. 파이썬은 기본 재귀 깊이 제한이 1000으로 매우 얕다고 한다. 따라서 재귀를 사용하여 문제를 풀 때에는 위의 코드를 넣어주어 재귀에러가 나는것을 막아주어야 한다. 이후에 코딩테스트에서도 이부분은 필수라고도 적혀있으니 기왕이면 외워두는게 좋..

dfs/bfs문제다. 문제를 크게 꼬거나 어렵게 만들지 않은 것 같다. dfs/bfs 둘중에 하나만 제대로 구현할 줄 알면 풀 수 있는 문제인 것 같다. 감염된 컴퓨터의 개수를 구하는 문제이므로 탐색문제에서는 시작점으로부터 방문한적이 있는 노드의 수를 카운팅하면 되는 문제이다. BFS를 이용한 풀이 # 2606번 바이러스 - bfs n = int(input()) m = int(input()) graph = [[0]*(n+1) for _ in range(n+1)] for _ in range(m): a,b = map(int,input().split()) graph[a][b] = graph[b][a] = 1 visited = [0]*(n+1) from collections import deque def bfs..

가장 기본적이고 DFS/BFS 개념문제라고 생각한다. DFS는 깊이우선탐색이라고 하여 그래프 자료구조를 그려놓고 수직의 방향으로 먼저 탐색하는 방법을 말한다. 재귀 혹은 스택 자료구조를 이용하여서 구현할 수 있다. BFS는 넓이우선탐색이라고 하여 그래프에서 수평방향으로 먼저 탐색하는 방법이라고 이해하면 될것 같다. 큐 자료구조를 이용하여 구현한다. # 1260번 # 입력값을 받는 부분 # 인접행렬로 그래프를 표현하였다. n,m,v = map(int,input().split()) graph = [[0]*(n+1) for _ in range(n+1)] for i in range(n+1): a,b = map(int,input().split()) graph[a][b] = graph[b][a] = 1 # DFS구..