Dev On The Coffee Dev On The Coffee

# 문제 내 풀이 # DFS 정의 def dfs(computers, v, visited, n): # 현재 노드를 방문 visited[v] = True # 현재 노드의 인접 노드를 재귀적으로 방문 for i in range(n): if computers[v][i] and not visited[i]: dfs(computers, i, visited, n) def solution(n, computers): answer = 0 visited = [False] * n # 각 노드의 방문 정보를 표현 # 첫번째 노드부터 순서대로 확인 for v in range(n): # 아직 방문하지 않은 노드라면 if not visited[v]: # dfs를 수행하고 네트워크 수를 하나 셈 dfs(computers, v, visi..

# 문제 N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. 내 풀이 - 문제 풀이 실패, 모범 답안 n, m = map(int, input().split()) graph = [list(map(int, input())) for _ in range(n)] # DFS로 특정 노드를 방문하고 연결된 인접 노드들 방문 def dfs(x, y): # 주어진 범위를 벗어나면 즉시 종료 if x ..

# 문제 내 풀이 - DFS와 BFS로 모두 구현해 봄 from collections import deque # bfs를 위한 큐 생성 라이브러리 import sys sys.setrecursionlimit(10000) # 파이썬 재귀 한도를 10000으로 늘림 (기존 재귀 한도: 1000) # dfs 정의 def dfs(x, y): graph[x][y] = -1 dx = [0, -1, 0, 1] dy = [1, 0, -1, 0] for i in range(4): next_x = x + dx[i] next_y = y + dy[i] if next_x = n or next_y = m: continue if graph[next_x][next_y] == 1: ..

# 문제 내 풀이 1 n = int(input()) graph = [list(map(int, input())) for _ in range(n)] # dfs 정의 def dfs(x, y, cnt): if x = n or y = n: return cnt if graph[x][y] == 1: graph[x][y] = -1 cnt += 1 cnt = dfs(x - 1, y, cnt) cnt = dfs(x + 1, y, cnt) cnt = dfs(x, y - 1, cnt) cnt = dfs(x, y + 1, cnt) return cnt return cnt h_cnt = 0 # 단지 개수 h_list = [] # 각 단지의 집의 개수 for i in range(n): for j ..

# 문제 내 풀이 from collections import deque import sys input = sys.stdin.readline # 조금 더 빠르게 입력 받기 n, m, v = map(int, input().split()) graph = [[] for _ in range(n + 1)] for i in range(m): n1, n2 = map(int, input().split()) graph[n1].append(n2) graph[n2].append(n1) # graph의 각각 노드에 대하여 인접한 노드 정보를 오름차순으로 정렬 for i in range(n + 1): graph[i].sort() dfs_visited = [False] * (n + 1) # dfs 방문 정보를 담을 배열 생성 bf..

# 문제 N * M 크기의 얼음틀이 있다. 구멍이 뚫려있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 X 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. 00110 00011 11111 00000 입력 첫 번째 줄에 얼음 틀의 새로 길이 N과 가로 길이 M이 주어진다.( 1

# 그래프 탐색 하나의 자료구조로서 그래프(Graph)는 데이터와 데이터 사이의 관계를 잘 표현해주는 자료구조이다. 그래프는 기본적으로 데이터가 담기는 노드(Node)와 데이터 사이를 연결하는 간선(Edge)으로 이루어져있다. 노드는 정점(Vertex)이라고도 불린다. 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말하며, 간선으로 연결되어 있는 두 노드는 서로 '인접'해 있다고 한다. # DFS (Depth-First Search, 깊이 우선 탐색) DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로로 먼저 최대한 깊숙이 탐색한 후, 다시 돌아와 다른 경로를 탐색한다. DFS는 스택이나 재귀함수를 활용해 구현하며, 기본 순서는 다음과 같다. 1. 탐색 시작 ..

# 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 ..