문제 N x N 크기의 2차원 배열이 있다. 2차원 배열의 i 행 j열에 해당하는 칸은 로 나타낸다. 처음에 이 배열의 각 칸에는 알파벳 대문자 또는 . 문자가 하나 적혀 있다. 상하좌우로 인접한 두 칸에 같은 문자가 적혀있는 경우, 두 칸은 연결되어 있다고 한다. 서로 연결된 칸들의 집합을 연결 요소라고 하고, 연결 요소의 크기는 그 연결 요소에 포함된 칸들의 개수와 같다. 구름이는 아래 작업을 Q번 수행하려고 한다. (y, x) 칸을 고른 뒤, 그 칸에 알파벳 대문자 를 쓴다. 구름이가 고른 칸은 . 문자가 적힌 칸임이 보장된다. 배열에 존재하는 모든 연결 요소의 크기를 계산한다. 만약 크기가 K 이상인 연결 요소가 존재한다면, 그 연결 요소에 포함된 모든 칸에 적힌 문자를 지운다. 모든 작업을 수행..
개발/CS/알고리즘
문제 플레이어는 1번부터 N번까지의 번호가 붙은 N개의 도시와 M개의 도로가 있는 나라에 살고 있다. 각 도로는 서로 다른 두 도시를 양방향으로 연결하고 있고, 주어진 도로만을 이용해 임의의 두 도시 사이를 이동하는 것이 가능하다. 플레이어는 차를 타고 S번 도시에서 E번 도시로 이동하려고 한다. 플레이어가 두 도시 사이를 이동할 때는 항상 가장 작은 수의 도시를 거치는 경로를 따라 이동한다. 예를 들어 아래 그림과 같이 도시와 도로가 주어지고, 플레이어가 1번 도시에서 4번 도시로 이동하려고 할 때는 항상 1 → 3 → 4의 경로를 따라 이동한다. 이 경우에는 출발 도시와 도착 도시를 포함해 총 세 개의 도시를 거쳐 이동할 수 있다. 1 → 5 → 2 → 4의 경로로 이동하는 것은 출발 도시와 도착 도..
문제 한 변의 길이가 N인 정사각형이 있다. 플레이어는 이 정사각형 위에 M개의 반직선을 그린 뒤, 두 반직선이 교차하는 점의 수를 세려고 한다. 플레이어가 반직선을 그리는 과정은 아래와 같다. 반직선을 그리기 시작할 칸 (y,x)를 정한다. (x,y)는 주어진 정사각형을 크기의 정사각형으로 나눴을 때,y 번째 행의 x번째 열에 해당하는 칸이다. 반직선을 그릴 방향 를 정한다. 방향은 상하좌우 중 하나이며, 항상 정사각형 테두리의 가로 혹은 세로와 평행하다. 반직선을 그린다. 반직선은 항상 시작 칸의 테두리에서부터 시작하며, 같은 칸을 지나는 평행한 직선이 서로 만나지 않도록 그린다. 풀이 def count_intersections(N, M, lines): vertical = [[0]*N for _ in..
문제 이 세상에는 수많은 컴퓨터들이 통신망을 통해 서로 연결되어 정보를 교류하고 있다. 오늘 플레이어는 이 거대한 통신망 중 한 구역을 조사하고자 한다. 플레이어가 조사할 구역에는 N개의 컴퓨터가 있고, M개의 통신 회선이 있다. 각 컴퓨터는 1번부터 N번까지 번호가 붙어 있고, 통신 회선은 서로 다른 두 컴퓨터를 양방향으로 연결하고 있다. 컴퓨터들은 연결 여부에 따라 여러 개의 컴포넌트로 나뉜다. 어떤 두 컴퓨터가 통신 회선만을 이용해서 연결되어 있다면 두 컴퓨터는 같은 컴포넌트에 속한다. 플레이어는 여러 개의 컴포넌트 중, 가장 밀도가 높은 컴포넌트를 조사하려고 한다. 컴포넌트의 밀도는 그 컴포넌트에 포함된 통신 회선의 개수를 컴퓨터의 수로 나눈 값이다. 주어진 통신 구역을 분석해서, 가장 밀도가 높..
Intro. 구름톤 챌린지로 오늘의 문제인, Goorm_연합을 풀이하였습니다 요즘은 코딩 테스트는 기본이라 꾸준히 풀고 있습니다. 확실하게 실력을 늘리려면, 다른 사람의 코드를 보거나, 제 코드에 대한 피드백을 받는거라 생각합니다 딱 GPT가 코드 인터프리터와 함께 사용하면 괜찮겠는데? 싶어 시작했습니다 내 코드 최적화 def find_union_iterative(N, M, graph): # Step 1: Initialize the graph g = defaultdict(set) for a, b in graph: g[a].add(b) # Step 2: Check for bidirectional links and create a union set visited = set() unions = [] def d..
문제 바다 위에 개의 섬이 있다. 섬은 1번부터 N번까지 차례대로 번호가 붙어 있다. 서로 다른 두 섬 사이를 연결하는 M개의 다리도 있다. 모든 다리는 단방향으로만 이동 가능하고, 어떤 두 섬 사이를 잇는 다리는 정방향 하나, 역방향 하나씩 해서 최대 두 개이다. 어느 날, 섬들 사이에 분쟁이 일어났다. 모든 섬들은 세력을 키우기 위해 다른 섬과 연합을 결성하려고 한다. 임의의 두 섬 와 에 대해, a번 섬에서 b번 섬으로 직접 이동할 수 있는 다리와 b번 섬에서 a번 섬으로 직접 이동할 수 있는 다리가 있으면, 두 섬은 연합을 결성한다. 이때, a와b 가 연합을 결성하고 b와 c가 연합을 결성했다면 와 역시 위 조건을 만족하지 않더라도 같은 연합에 속해있는 것으로 본다. 다른 섬과 연합을 결성하지 않..
문제 N개의 노드와 M개의 양방향 간선으로 이루어진 그래프가 있다. 이 그래프의 노드는 1번부터 N번까지 번호가 붙어 있다. 양끝 노드가 동일한 간선은 주어지지 않는다. 플레이어는 아래 규칙에 따라 그래프에서 이동하려고 한다. 플레이어는 처음에 K 번 노드에 있다. 한 번 방문한 노드는 다시 방문할 수 없다. 시작 노드도 방문한 것으로 간주한다. 현재 노드와 간선으로 직접 연결된 다른 노드 중, 방문할 수 있으면서 번호가 가장 작은 노드로 이동한다. 플레이어가 더 이상 이동할 수 있는 노드가 없을 때, 방문한 서로 다른 노드의 개수와 마지막 노드 번호를 구해보자. 풀이 from collections import defaultdict def solve(N, M, K, edges): # Initialize ..
문제 풀이 from collections import deque def bfs(n,k,grid): dic = {} directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] m = [[False for _ in range(n)] for _ in range(n)] for i in range(n): for j in range(n): current = grid[i][j] if current not in dic: dic[current]=0 count=1 if not m[i][j]: m[i][j]=True queue = deque([(i, j)]) while queue: x, y = queue.popleft() for dx, dy in directions: nx, ny = x + dx,..
문제 풀이 from collections import deque # Python 코드로 문제 해결 알고리즘 구현 (BFS 사용) def min_generators(n, grid): # 발전기 개수 초기화 generator_count = 0 # 전력 공급 상태를 저장할 리스트 초기화 supplied = [[False for _ in range(n)] for _ in range(n)] # BFS를 위한 방향 벡터 directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 모든 칸을 순회 for i in range(n): for j in range(n): # 집이 있는 칸을 찾음 if grid[i][j] == 1 and not supplied[i][j]: # 전력이 공급되지 않은..
폭탄 구현하기 2 N,K = map(int,input().split()) mp = [list(input().split()) for _ in range(N)] m = [[0 for _ in range(N)] for _ in range(N)] def check(y,x): y-=1 x-=1 global mp,m if y
