본문 바로가기
728x90

분류 전체보기653

백준 2667번: 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고.. 2022. 7. 14.
백준 7569번: 토마토 (3차원배열) https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 .. 2022. 7. 14.
백준 7576번: 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 .. 2022. 7. 14.
백준 2606번: 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 .. 2022. 7. 13.
백준 2178번: 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 .. 2022. 7. 13.
백준 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 1.. 2022. 7. 13.
BFS - 미로 찾기 이코테 p.152 - 미로찾기 N x M 크기의 미로가 있다. (1,1)에서 (N,M)으로 가기위한 최소 이동 칸 수를 구하라. 괴물(0), 길(1) BFS를 이용하고.. 방문한 노드는 (이전 노드값+1)을 해서 방문표시를 한다. (N,M)위치의 노드 값을 읽으면 최소 발자취 수가 나온다. from collections import deque dx=[1,-1,0,0] dy=[0,0,-1,1] def bfs(x,y): queue = deque() queue.append((x,y))#현재 노드 방문처리 while(queue): x, y= queue.popleft() #큐에서 좌표를 꺼냄 for i in range(4):#상하좌우 네방향 확인 nx=x+dx[i] ny=y+dy[i] if nx=N or ny=M.. 2022. 7. 13.
백준 1012번: 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어,.. 2022. 7. 13.
DFS - 음료수 얼려 먹기 이코테 p.149 N X M 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 있는 부분은 1로 표시된다. 구멍이 뚫린 부분끼리 상, 하, 좌, 우로 붙어있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 입력 조건 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로길이 M이 주어진다 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다 이때 구멍이 뚫린 부분은 0, 그렇지 않은 부분은 1이다 출력 조건 한 번에 만들 수 있는 아이스크림의 개수를 출력한다 기록 1. 상하좌우로 탐색하는 dfs함수 구현 2. 각 칸에 대하여 dfs를 수행하고, 그 칸이 방문하지 않은 곳이면 result값을 1 증가시킴 3.. 2022. 7. 13.
백준 1202번: 보석 도둑 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그.. 2022. 7. 13.
탐색 알고리즘 - BFS from collections import deque #BFS메서드 정의 def bfs(graph,start,visited): #큐 구현을 위해 deque 라이브러리 사용 queue = deque([start]) #시작 노드를 큐에 넣음 visited[start]=True #현재 노드 방문처리 #큐가 빌 때까지 반복 while queue: #큐에서 원소를 하나 뽑아 출력 v= queue.popleft() print(v,end=' ') for i in graph[v]: #뽑은 원소의 주변 노드 if not visited[i]:#방문하지 않았으면 queue.append(i) #큐에 삽입 visited[i]=True #삽입한 노드는 방문처리 #각 노드가 연결된 정보를 2차원 리스트로 표현 graph=[ [],.. 2022. 7. 12.
탐색 알고리즘 - DFS DFS (Depth-First Search, 깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. def dfs(graph, v, visited): visited[v] = True print(v,end=' ') for i in graph[v]: if not visited[i]: dfs(graph,i,visited) #각 노드가 연결된 정보를 2차원 리스트로 표현 graph=[ [],#1번 [2,3,8], [1,7,], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] #각 노드의 방문이력을 저장할 1차원리스트 visited=[False]*9 dfs(graph,1,visited) def dfs(graph, v, visited): visited[v] = T.. 2022. 7. 12.
식물 키우기 2월 28일 오후1시 다이소 원예코너에서 사온 재료들... 다 합쳐서 칠천원 정도였나... 되게 저렴하고 좋았음... 22.03.12. 씨앗 심은지 2주만에 이만큼 자랐다. 너무 다닥다닥 붙어있어서 딱 4개만 빼고 다 솎아냈다... 2022. 7. 12.
728x90

티스토리툴바