생각하다 생각하다

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] # 노드가 미로 범위..

4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net >문제 >접근방법 결국 섬의 개수를 세는 거니까 정사각형을 전체에서 섬이 있는 곳을 발견 할 때마다 재귀 dfs로 탐색하고 발견하면 count를 1 더하면 된다. 재귀 dfs 함수 안에서는 상하좌우 대각선 네 방면까지 탐색하고 방문한 경우에는 0으로 바꿔준다. >풀이법 주석으로 대체 >코드 # 런타임 에러 (RecursionError) 방지 import sys sys.setrecursionlimit(10**6) # 좌표가 (0, 0)일 때를 기준으로 상하좌..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net >문제 >접근방법 트리도 그래프의 유형 중 하나이기 때문에 bfs를 이용한다. 부모노드에 인접한 노드를 자식노드로 간주하고, 자식노드 인덱스의 값을 부모노드로 채워준 리스트를 만들어서 출력하면 된다. >풀이법 주석으로 대체 >코드 from collections import deque n = int(input()) # 노드의 개수 tree = [[]*n for _ in range(n+1)] # 트리의 노드 정보 queue = deque([]) # 큐의 원소는 부모노드의 역할 visited = [False for _ in rang..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net >문제 >접근방법 감이 상하좌우의 감을 익히기 때문에 깊이우선탐색을 사용한다. 하루가 지날 때마다 감이 있는 위치에 1을 더해준다. bfs가 끝났을 때 가장 큰 숫자가 토마토가 모두 익을 때까지의 최소 날짜이다. >풀이법 1. 2차원 리스트 box 생성 후 상자에 담긴 토마토들의 정보를 입력받는다. 2. 상자 중에서 1이 담긴 모든 위치를 큐에 삽입한다. (이때 좌표를 입력받으므로 큐의 요소는 리스트([])로 생성한다) 3. 큐의 원소를 꺼내 좌..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net >문제 >접근방법 2차원 리스트에 밭을 구현하고 배추를 심은 곳에만 1을 넣는다. 1인 곳에서 상하좌우를 탐색해서 배추흰지렁이 마리 수 세기. >풀이법 1. 밭의 크기만큼 2차원 리스트를 생성한다. 2.입력받은 배추 위치에 1을 넣어준다. 3. 밭을 반복문으로 인덱스 하나씩 검색해서 1인 경우에 search함수를 실행한다. 4. search함수는 1의 상하 좌우가 0 일 때까지 재귀적으로 탐색하고, 탐색이 끝난 자리는 0으로 값을 변경해준다. 5. search가 한 번 수..

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net >문제 >접근방법 그래프 탐색 dfs, bfs 사용하기 >풀이법 1) 깊이우선탐색(반복)[DFS] 1. 2차원 리스트 생성 후 입력값 append 2. dfs함수 - 스택을 이용한 깊이우선탐색 수행 3. dfs의 리턴값 visit의 개수에서 1을 뺀 값 출력 2) 깊이우선탐색(재귀)[DFS] 1. 2차원 리스트 생성 후 입력값 append 2. dfs함수(재귀) - dfs함수를 재귀적으로 호출 3. visit 대신 한 번 dfs를 수행할 때마다 count에 1을 더해..

1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net >문제 >접근방법 시간초과를 면하려면 모든 문자열을 검사하는 것이 아니라 중복된 문자를 모두 빼고 남은 문자열을 검사해야한다. count로 알파벳 개수를 세고 temp보다 크면 temp에 넣는다. >풀이법 1. ch에 문자열을 입력받은 후 모두 대문자화 해준다. upper() 2. ch2에 입력받은 문자열에서 중복을 제거해서 넣어준다. join(set()) 3. ch2의 모든 요소의 개수를 세고 비교해보면서 가장 큰 값은 temp에 넣는다. 4. temp가 갱신될 때마다 ch2[i]를 out에..