백준

백준 1697 숨바꼭질 (BFS)

이거 어렵지는 않았다. 그냥 BFS로 원하는 목표치가 나올때까지 갯수를 확인하면서 루프를 돌리면 된다. 내가 헤맨 부분은 이동할때 2배로 이동하는 부분이 존재하기 때문에 start 점과 end점을 (start = 0 and visited[t-1]==0: tmp.append(t-1) visited[t-1] = 1 if t+1

백준 7576 토마토 (BFS, 행렬 그래프, python)

이번 문제는 원리도 파악하고 간단히 풀수 있다고 생각하고 코딩을 진행했다. 모든 예를 통과하고 반례도 통과하며 잘 코딩했다고 생각했으나 시간초과의 벽을 넘지 못하고 고수들의 코드를 보게 되었다. 원리는 어렵지 않다. 1. 토마토가 존재하는 곳을 찾아서 큐에 넣어준다. 2. 큐에서 하나씩 꺼내며 너비탐색을 진행한다. 3. 탐색이 끝나면 익지 않은 토마토가 존재하는지 확인한다. 4. 전부 익었다면 걸린 날짜를 출력, 익지 않은게 있다면 -1을 출력한다. 이를 토대로 코딩을 진행했다. 그러나 아래의 코드는 시간초과로 쓸수가 없었다. from collections import deque m,n = map(int, input().split()) L = [] for _ in range(n): tmp = list(m..

백준 2178 미로 탐색 (BFS, 최단 경로 탐색, 행렬그래프)

이번 문제는 BFS를 어떻게 최단경로로 활용할건지 이해해야한다. 처음에는 나도 BFS로 어떻게 최단경로를 구한다는 소리인지 알 수 없었다. 나도 완벽하게 이해하고 풀지 않았기 때문에 생각의 흐름을 나열해 볼까 한다. 우선 행렬그래프를 BFS의 트리 형태로 나열한다고 가정한다면 다음과 같은 그래프를 만들 수 있다. 그렇다면 우리는 (4,4)가 되기 위해서 7층까지 내려가야한다는 것을 단숨에 확인 가능하다. 그렇다면 BFS로 탐색을 하면서 언제가 몇층인지를 알아야한다. 따라서 층을 함께 표기해본다. 그러면 (1,1)이 1층인것을 알기 때문에 층에 큐에 넣은 인접 행렬에 대해서 2층이라는 것을 표기하여 큐에 삽입할 수 있다. 이러한 방식으로 (4,4)까지 진행하면 간단히 (4,4)가 7층에 있는 것을 알 수 ..

백준 1012 풀이 (유기농 배추, DFS, 행렬)

2667번과 아주 흡사하다.(guccin.tistory.com/89?category=977502) 그나마 다른점은 정사각형 행렬이 아니라 직사각형 행렬이라는점 뿐이다. 그래서 2667의 DFS함수를 그대로 가져와서 사용할 수 있었다. 코드는 2667과 거의 유사하고 다른점은 배추의 포인트를 직접 갱신 시켜준다는 점과 패딩을 직사각형에 맞춰주는 것 밖에는 없다. 그래서 2667을 이해하면 그냥 껌이 되버리는 문제이다. 풀이 쓰는 시간이 아까우니 바로 코드를 첨부한다. def DFS(i, j, L): stack = [(i,j)] out = [] while stack: t = stack.pop() a,b = t if t not in out: out.append(t) L[a][b] = 0 # 지워버려 #위쪽 오..

백준 2667 단지번호붙이기 (DFS, 그래프 탐색)

이번 문제는 생각보다 쉽게 풀렸다. DFS의 기본 코딩 구조를 알면 바로 대입이 가능한 문제였다. 문제는 1이 집들이고 붙어 있는 집끼리 단지를 조성한다. 그리고 단지의 개수를 확인하고 단지별 개수를 오름차순으로 출력하는 문제이다. 이 문제를 풀기 위해서는 뇌피셜로 필요하다고 생각되는 요소를 정리해 보았다. 1. DFS를 스택을 활용하여 코딩을 구현할 수 있는지 2. DFS로 행렬들의 인접을 어떻게 파악할건지 3. 다음 단지는 어떻게 찾을건지 우선 DFS를 스택을 활용하여 코딩하는건 넘어간다. 그럼 2번 DFS로 행렬들의 인접을 어떻게 파악할건지 생각해본다. 현재 (0,1)에서 가장 먼저 집이 발견된다. 문제는 동서남북 모두 확인하여 인접한 행렬을 확인해야 하는데 위에는 접근할 수가 없다. 따라서 에 패..

백준 2606 바이러스 (DFS)

이번에는 저번에 공부한 것을 토대로 DFS를 구현하는 문제이다. 오히려 저번 문제보다 쉬운게 함정이다. 1번 컴퓨터가 감염될때 감염되는 컴퓨터의 수는 4이다. 따라서 숫자만 구해주면 된다. DFS로 풀게되면 1->2->3->5->6순으로 가게 된다. 그런데 우리는 순서는 중요하지 않아서 stack에 넣어줄때 그냥 때려 넣기만 하면 된다. 따라서 1260 문제 (guccin.tistory.com/87)보다 쉽게 코딩이 가능하다. n = int(input()) m = int(input()) graph = {} for i in range(m): a,b = map(int, input().split()) if a not in graph: graph[a] = [b] else: graph[a].append(b) if..

백준 1260 풀이 (DFS, BFS, 그래프 탐색)

이번 문제는 그래프 탐색 문제이다. 그래프가 주어지면 이것을 DFS,BFS방식으로 탐색하여 순서를 나타내면 된다. DFS, BFS의 개념은 알고 있었지만 막상 코딩으로 짜려니 상당히 헤매었다. DFS를 설명하자면 깊이 우선 탐색방법으로 깊게 들어가는 가며 탐색하는 방법이다 원리는 구글에 자세히 나온다. 처음 도움을 받은 곳은 www.youtube.com/watch?v=_hxFgg7TLZQ 로 영상을 보고 대강 이해를 하고 코드를 짜기 시작했다. 간단히 설명하자면 DFS => stack으로 탐색 가능. 연결되는 노드를 차례로 스택에 저장 BFS => queue로 탐색 가능. 연결되는 노드를 차례로 큐에 저장 자세한 로직은 유튜브를 참고하면 될것이다. 물론 유튜브 과정 그대로 코딩을 하려니 코드가 길고 더러..

백준 11049 (행렬 곱셈 순서, DP)

처음에 보고 먼소린가 했는데 행렬의 곱셈이 이루어진 후의 연산 비용을 계산해보는 문제이다. 따라서 최소값을 구하면 된다. 그럼 식을 세워야 한다. 저번에 풀었던 11066문제와 비슷하다. 양옆으로 연산을 하기 때문에 잘 쪼개서 계산하면 된다. 그래서 일반항으로 나타내면 아래와 같다. 아주 다행인건 최적화 따위를 안해도 된다는 것이다. 여기서 팁은 최솟값이 적어도 2^31-1보다 작아야한다는 것이다. 따라서 이부분을 놓치지 않고 코딩으로 바꾸어 주면 아래와 같다. n = int(input()) p = [] for i in range(n): p.append(tuple(map(int, input().split()))) D = [[0 for i in range(n)] for i in range(n)] # 연산시..