문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 접근 대각선상에 집이 있는 경우는 연결된 것이 아니므로, 상하좌우로 탐색하는 dfs다. 코드 n = int(input()) grid = [list(map(int, list(input()))) for _ in range(n)] ..
💬 문제 (leetcode.com/problems/employee-importance/) You are given a data structure of employee information, which includes the employee's unique id, their importance value and their direct subordinates' id. For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like..
문제 There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return ..
www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 처음에는 모든 경로 탐색하는 문제에 익숙해져있어서 DFS를 사용해서 구현했다가 시간초과로 실패했다. 그래서 알아보니 BFS와 DFS에는 다음과 같은 차이가 있었다. BFS : 최단 경로를 보장한다. 두 노드간의 최단(임의) 경로를 찾고 싶을 때 사용한다. 큐를 사용한다. 재귀를 통해 구현할 수 없다. DFS : 모든 경로를 탐색한다. → 시간복잡도가 매우 커진다. BFS 보다 구현이 간단하다. 스택을 사용한다. 재귀를 통해 구현할 수 있다. ..
