2667번과 유사한 문제로 구하는 값이 다르다 여기서는 묶을의 개수만 구하면 된다 문제를 풀때 좌표를 잘 생각해서 풀어야한다 x,y의 그래프가 x축 기준으로 반전이어서 인덱스를 잘 설정하지 않으면 인덱스 오류가 나오기 쉬운 문제이다 from collections import deque import sys input = sys.stdin.re...

숫자열을 입력 받고 받은 숫자열을 가로 세로끼리 이어서 하나의 묶음을 만들어야 한다 문제에서는 하나의 묶음을 단지로 표현했다 하나의 좌표에서 왼쪽 오른쪽 위아래로 움직였을때 만약 해당 위치의 값이 1이라면 서로 이어진 곳이다 이렇게 이어진 곳이 몇개있는지 알아내는 문제이다 입력할 때 띄어쓰기로 구분이 되어있지 않아서 그 부분도 해결해야한다 ...

DFS와 BFS를 모두 사용해서 두가지의 경우를 출력해야한다 하지만 예제 출력을 보면 이때까지 출력했던 방법과 다르게 노드의 순서에 따라 방문순서를 출력하는게 아니라 방문순서에 따라 노드번호를 출력해야한다 DFS와 BFS를 동시에 사용하기 때문에 변수를 겹치지 않게 각각 잘 설정해주어야 한다 출력 부분을 조심하면 어려운것은 없다 #n,m,v...

DFS,BFS를 이용한 문제 풀이 바이러스에 감염된 컴퓨터에 연결된 컴퓨터를 모두 찾아서 그 숫자를 세면된다 DFS나 BFS중 가중치를 1로 계산해서 마지막 가중치에서 처음 감염된 컴퓨터를 빼줌 (-1) 그러면 감염된 컴퓨터의 총 개수가 나온다 너비 우선탐색 (BFS) #bfs 풀이 from collections import deque im...

너비 우선 탐색문제는 깊이 우선탐색과 다르게 가로로 먼저 움직이는것이다 기준 노드에서 가장 얕은 노드부터 가장 깊은 노드로 탐색 하는 방법이다 너비우선 탐색은 시작점에서 가까운것을 기준으로 탐색하기 때문에 최단경로를 찾을 때 유용하다   from collections import deque import sys input = sys....

이전문제와 완전히 동일하지만 오름차순 탐색에서 내림차순 탐색으로 변경된 문제이다     오름차순으로 정렬할때는 list.sort()이지만 내림차순으로 정렬할 때는 reverse=True가 필요하다 def dfs(k): #방문 순서를 ans리스트에 기록한다 global cur ans[k] = cur for to_g...

깊이 우선탐색 문제로 깊이 우선 탐색이란 노드에서 좌우로 움직이는 것(bfs)이 아닌 세로로 움직이는것이다 한방향을 계속 가다가 더이상 가지 못하면 다시 가장 가까운 갈림길로 돌아와서 이곳부터 다시 탐색을 진행하는 방법이다 넓게보다는 깊이를 우선적으로 탐색 모든 노드를 방문하고자 하는 경우 사용한다 ...

이전 문제인 최소 힙과 최대 힙하고 비슷한 문제이지만 이 문제에서는 절대값으로 저장을 한다 따라서 숫자를 받을때 음수와 양수를 어떻게 처리하는지가 중요하다   절대값으로 숫자를 받아서 정리하지만 출력할 때는 음수와 양수를 구분해서 출력해야한다 그래서 처음에 다른 리스트(원본 저장)를 추가로 만들어서 그곳에 입력 받은 원소를 저장하고 힙에는 ...

최소 힙 문제로 이전 문제 최대 힙과 같은 문제이다 최대 힙을 구현할때는 음수로 지정해서 힙에 넣었지만 이번에는 그냥 넣으면 최소 힙이 바로된다   우선 순위 큐 우선 순위 큐란 일반적인 큐(FIFO)와 다르게 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 큐이다 우선 순위 큐는 힙구조로 구현이 되어있다 우선 순위 큐 EX...

이번 문제는 우선 순위 큐를 이용한 문제이다 우선순위 큐에서 최대 힙을 이용한다 파이썬에 내장된 함수 heapq를 이용해서 쉽게 풀 수 있었다   우선 순위 큐 우선 순위 큐란 일반적인 큐(FIFO)와 다르게 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 큐이다 우선 순위 큐는 힙구조로 구현이 되어있다 우선 순위 큐 EX...