문제 N x N 크기의 2차원 배열이 있다. 2차원 배열의 i 행 j열에 해당하는 칸은 로 나타낸다. 처음에 이 배열의 각 칸에는 알파벳 대문자 또는 . 문자가 하나 적혀 있다. 상하좌우로 인접한 두 칸에 같은 문자가 적혀있는 경우, 두 칸은 연결되어 있다고 한다. 서로 연결된 칸들의 집합을 연결 요소라고 하고, 연결 요소의 크기는 그 연결 요소에 포함된 칸들의 개수와 같다. 구름이는 아래 작업을 Q번 수행하려고 한다. (y, x) 칸을 고른 뒤, 그 칸에 알파벳 대문자 를 쓴다. 구름이가 고른 칸은 . 문자가 적힌 칸임이 보장된다. 배열에 존재하는 모든 연결 요소의 크기를 계산한다. 만약 크기가 K 이상인 연결 요소가 존재한다면, 그 연결 요소에 포함된 모든 칸에 적힌 문자를 지운다. 모든 작업을 수행..
개발/CS/OS
문제 플레이어는 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번까지 번호가 붙어 있고, 통신 회선은 서로 다른 두 컴퓨터를 양방향으로 연결하고 있다. 컴퓨터들은 연결 여부에 따라 여러 개의 컴포넌트로 나뉜다. 어떤 두 컴퓨터가 통신 회선만을 이용해서 연결되어 있다면 두 컴퓨터는 같은 컴포넌트에 속한다. 플레이어는 여러 개의 컴포넌트 중, 가장 밀도가 높은 컴포넌트를 조사하려고 한다. 컴포넌트의 밀도는 그 컴포넌트에 포함된 통신 회선의 개수를 컴퓨터의 수로 나눈 값이다. 주어진 통신 구역을 분석해서, 가장 밀도가 높..
문제 바다 위에 개의 섬이 있다. 섬은 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]: # 전력이 공급되지 않은..
구름 찾기 깃발 N,K = map(int,input().split()) mp = [list(map(int,input().split())) for _ in range(N)] m = [[0 for _ in range(N)] for _ in range(N)] def check(x, y): global m for i in range(x-1,x+2,1): for j in range(y-1,y+2,1): if i
문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15..
