생각하다 생각하다

백준 10813. 공 바꾸기 _Java 🧶 문제 설명 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 바구니에는 공이 1개씩 들어있고, 처음에는 바구니에 적혀있는 번호와 같은 번호가 적힌 공이 들어있다. 도현이는 앞으로 M번 공을 바꾸려고 한다. 도현이는 공을 바꿀 바구니 2개를 선택하고, 두 바구니에 들어있는 공을 서로 교환한다. 공을 어떻게 바꿀지가 주어졌을 때, M번 공을 바꾼 이후에 각 바구니에 어떤 공이 들어있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐서 공을 교환할 방법이 주어진다. 각 방법은 두 정수 i j로 이루어져 있으며, i번 바..

백준 10810. 공 넣기 _Java 🧶 문제 설명 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 들어있지 않으며, 바구니에는 공을 1개만 넣을 수 있다. 도현이는 앞으로 M번 공을 넣으려고 한다. 도현이는 한 번 공을 넣을 때, 공을 넣을 바구니 범위를 정하고, 정한 바구니에 모두 같은 번호가 적혀있는 공을 넣는다. 만약, 바구니에 공이 이미 있는 경우에는 들어있는 공을 빼고, 새로 공을 넣는다. 공을 넣을 바구니는 연속되어 있어야 한다. 공을 어떻게 넣을지가 주어졌을 때, M번 공을 넣은 이후에 각 바구니에 어떤 공이 들어 있는지 구하는 프로그램을 작성하..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net >문제 >접근방법 그래프 전체를 탐색하면서 1인 부분은 재귀적 깊이우선탐색을 수행한다. 한 단지를 다 탐색하면 집의 수를 리스트에 추가하고 sort로 오름차순으로 정렬해준다. 여기서 리스트의 길이가 곧 단지의 수가 된다. >풀이법 주석으로 대체 >코드 import sys # 런타임 에러(재귀 에러) 예방을 위해 재귀에 제한을 줌 sys.setrecursionlimit(10**6) input = sys.stdin.readline # 상하좌우 탐색용 인덱스 변수 d..

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net >문제 >접근방법 그래프 탐색으로 한 번 탐색이 종료될 때마다 count 개수를 세면 되겠다. >풀이법 주석으로 대체 >코드 1) bfs로 푼 코드 import sys from collections import deque # 시간초과 방지를 위한 코드 (input()으로 입력받으면 시간초과가 뜸) input = sys.stdin.readline # 노드와 간선의 개수를 각각 입력 받기 n, m = ma..

2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net >문제 >접근방법 친척 관계를 그래프라고 생각하고 방문할 때마다 방문하기 이전 노드의 방문 횟수를 쌓아간다. >풀이법 주석으로 대체 >코드 import sys # 런타임에러(재귀오류) 방지용 코드 sys.setrecursionlimit(10**6) # 전체 사람 수 입력 받기 n = int(input()) # 촌수를 계산 할 두 사람의 번호 입력 받기 a, b = map(int, input().split()) # 부모자식들 간의 관계 개수 ..

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net >문제 >접근방법 dfs로 풀었다. 구역 전체를 탐색하면서 상하좌우를 방문해서 이전 문자와 같으면 다시 상하좌우 탐색 재귀를 반복하는 식으로. 구역 전체 탐색을 총 두 번 하는데 처음 탐색할 때 G인 값은 R로 바꿔준다. 그리고 바꾼 구역을 두 번째로 탐색할 때의 값은 적록색약이 있는 사람의 기준이 된다. >풀이법 주석으로 대체 >코드 import copy import sys # 런타임에러(재귀오류) 방지 sys.setrecursionlimit(10**6)..

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net >문제 >접근방법 비의 양이 정해져있지 않아서 1부터 100까지 다 해보고 안전 영역이 제일 많이 나온 경우의 수를 출력한다. 안전 영역의 개수를 세야하기 때문에 dfs를 사용한다. 지역 전체를 탐색하다가 비의 양보다 높을 경우에만 dfs를 수행하면 된다. 수행될 때마다 temp를 하나씩 더해주고 dfs가 끝난 후에 temp의 개수가 count 보다 클 경우 count를 temp의 값으로 교체한다. >풀이법 주석으로 대체 >코드 import sys import copy..

백준 2178. 미로 탐색 _Python >접근방법 토마토 풀었을 때랑 거의 같다. 너비우선탐색 bfs로 인접한 노드로 옮겨갈 때마다 카운트를 누적해 가면서 값을 누적된 카운트 값으로 변경해준다. 그리고 N, M 인덱스의 값을 출력시키면 된다. >풀이법 주석으로 대체 >코드 import sys from collections import deque # 인접노드 탐색용 인덱스 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 미로의 최단거리를 구하는 함수 def bfs() : while queue: a, b = queue.popleft() # a와 b의 상하좌우 인접한 노드 탐색 for l in range(4): nx, ny = a + dx[l], b + dy[l] # 노드가 미로 범위..