전체 글

1. 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다. 2. 풀이 BFS 알고리즘을 활용하여 풀이할 것이다. BFS 하면 queue바로 떠올려야 하고 queue하면 deque가 바로 떠올라야 한다. 행렬 역시 그래프로 생각할 수 있으므로 주어진 행렬을 그래프에 저장한다. 그래프에서 (N, M)까지 가는 길은 연결되어 있으므로 BFS 함수는 한번만 호출해주면 된다. BFS..

1. 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1로 구성된 영역이 총 몇개가 있는지 찾는 문제이다. 상, 하, 좌, 우 중 하나가 연결되어 있다면 인접한 것이고 같은 영역으로 카운트 된다. 하지만 4방향 중 어느 하나에도 연결되어 있지 않다면 인접하지 않은 것이고 다른 영역으로 카운트 해줘야 한다. 2. 풀이 BFS를 이용하여 풀이할 것이므로 deque를 활용할 것이다. 그래프를 탐색하기 위해 x, y좌표를 변화시킬 때 사용할 리스트가 필요하다..

1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 저번에 풀었던 문제이다. 지난번 포스팅 링크: https://daily-stack.tistory.com/70 [Python]Baekjoon 2606번: 바이러스(BFS) 1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨..

1. 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 1번 컴퓨터와 연결된 컴퓨터가 몇 개인지를 구하는 문제이다. 첫 그래프 탐색 문제이다. 2. 풀이 우선 BFS를 이용하여 풀이하여 보자. 파이썬에서 queue를 구현할 때는 list가 아닌 deque를 활용하는데 그 이유는 시간 복잡도 측면에서 deque가 유리하기 때문이다. 리스트를 활용하여 큐를 구현할 수는 있지만, 큐의 연산을 수행할 때(리스트의 앞쪽에서 요소를 삭제하거나 추가할 때) ..

간단한 DFS 구현해 보기 깊이 우선 탐색 알고리즘인 DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다는 특징이 있다. 또한 DFS는 스택을 이용하는 알고리즘 이기 때문에 실제 구현은 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. 예제 코드는 다음과 같다. # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end= '') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph , i , visi..

1. 문제 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 키와 몸무게가 주어졌을 때, 각 사람들의 덩치 순위를 구하는 문제이다. 키와 몸무게 모두 커야 '덩치가 크다'라고 할 수 있으며, 키, 덩치 둘 중에 하나만 크다면 같은 순위가 된다. 각 사람들의 덩치 순위를 한 줄에 공백을 사이에 두고 출력하면 된다. 2. 풀이 '순위'라는 것은 '나보다 뛰어난 사람이 몇 명 있는가?'라는 의미로 생각할 수 있다. 즉, 나보다 덩치가 큰 ..