알고리즘/백준
[백준 알고리즘] 11725번 트리의 부모 찾기, 파이썬(python)
[백준 알고리즘] 11725번 트리의 부모 찾기, 파이썬(python)
2021.08.2611725, 트리의 부모 찾기 📁 문제 출처 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 💡 생각 노드 형태의 bfs 문제 풀이 parent 배열을 만들어줘서 노드의 부모 표시 🛠 나의 코드 from collections import deque import sys input = sys.stdin.readline n = int(input()) graph = [[] for _ in range(n+1)] parent = [0 for _ in range(n+1)] def bfs(start): queue = deque() queue.append(start) while queue:..
[백준 알고리즘] 3184번 양, 파이썬(python)
[백준 알고리즘] 3184번 양, 파이썬(python)
2021.08.263184, 양 📁 문제 출처 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 💡 생각 용어 정리 . (점)은 빈 필드 #는 울타리 o는 양 v는 늑대 조건 정리 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다. 양은 늑대에게 싸움을 걸 수 있다. 영역 안의 양의 수 > 영역 안의 늑대의 수 = 양 win, 늑대 out 그렇지 않다면 늑대 eat 양 생각하기 어떻게 울타리 영역을 구분해서 안에 있는 양과 늑대의 수를 count 할 것인가? graph[i][j] in 'o..
[백준 알고리즘] 10026번 적록색약, 파이썬(python)
[백준 알고리즘] 10026번 적록색약, 파이썬(python)
2021.08.2510026, 적록색약 📁 문제 출처 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 💡 생각 graph를 입력받고 G를 R로 모두 바꿔주는 새로운 배열을 만들어준다. graph[i][j] in 'RGB'면 bfs함수 실행하면서 count 해주기 🛠 나의 코드 from collections import deque n = int(input()) graph = [] graph_red = [['0'] * n for i in range(n)] for i in range(n): graph.append(list(in..
[백준 알고리즘] 2468번 안전 영역, 파이썬(python)
[백준 알고리즘] 2468번 안전 영역, 파이썬(python)
2021.08.252468, 안전 영역 📁 문제 출처 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 💡 생각 문제 이해를 못해서 다른 사람들의 풀이를 여러 번 보고 이해할 수 있었다. "안전한 영역의 최대 개수", "아무 지역도 물에 잠기지 않을 수도 있다." 이 두 문장이 문제의 핵심이다. 일단 비가 얼마나 오는지 모른다. -> 비가 오는 양은 0부터 배열에 있는 최고 높이까지 온다. 최고 높이까지 오면 모두 잠기기 때문에 최고 높이-1 까지만 계산한다. 예를 들면 최고 높이가 9라면 0부터 8까지 다 돌고 안전한 영역의 최대 개..
[백준 알고리즘] 2583번 영역 구하기, 파이썬(python)
[백준 알고리즘] 2583번 영역 구하기, 파이썬(python)
2021.08.242583, 영역 구하기 📁 문제 출처 💡 생각 예시에 있는 그래프를 위로 뒤집으면 좌측 상단이 (0, 0)인 그래프가 된다 그렇다면 입력을 받을 때 x1, y1, x2, y2 이렇게 받고 그래프에 그려줄 때는 2중 for문으로 (y1, y2) (x1, x2) 이렇게 받으면 예시와 같은 그래프를 그려줄 수 있다. 🛠 나의 코드 from collections import deque import sys input = sys.stdin.readline m, n, k = map(int, input().split()) dx = [0, 0, 1, -1] dy = [1, -1, 0 , 0] def bfs(graph, a, b): queue = deque() queue.append((a, b)) graph[a][b] =..
[백준 알고리즘] 7562번 나이트의 이동, 파이썬(python)
[백준 알고리즘] 7562번 나이트의 이동, 파이썬(python)
2021.08.247562, 나이트의 이동 📁 문제 출처 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 💡 생각 나이트가 현재 위치에서 원하는 위치까지 최소 몇 번 이동해야지 도착할 수 있는지를 구하는 문제이다. 현재 위치에서 목적지까지 어떻게 가는가? -> [2178, 미로 탐색] 문제처럼 라벨링을 해주면서 진행 🛠 나의 코드 from collections import deque import sys input = sys.stdin.readline dx = [-1, -2, -2, -1, 1, 2, 2, 1] dy = [2, 1..
[백준 알고리즘] 4963번 섬의 개수, 파이썬(python)
[백준 알고리즘] 4963번 섬의 개수, 파이썬(python)
2021.08.224963, 섬의 개수 📁 문제 출처 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 💡 생각 입력은 while문으로 계속 받기 대신 다른 bfs문제와 달리 대각선으로도 이동이 가능하기 때문에 기존 상하좌우에서 4가지 경로를 더 주었다. dx = [0, 0, 1, -1, 1, -1, 1, -1], dy = [1, -1, 0, 0, 1, -1, -1, 1] 🛠 나의 코드 from collections import deque import sys input = sys.stdin.readline dx = [0, ..
[백준 알고리즘] 11724번 연결 요소의 개수, 파이썬(python)
[백준 알고리즘] 11724번 연결 요소의 개수, 파이썬(python)
2021.08.2111724, 연결 요소의 개수 📁 문제 출처 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 💡 생각 방향이 없는 그래프는 graph[a].append(b), graph[b].append(a)로 양방향을 넣어주고 큐에 넣어주면서 모든 노드를 검사하면 된다. 쭉 연결이 되어 있다면 bfs함수 한 번에 끝나지만, 연결이 끊기면 다시 돌아와서 bfs 함수 실행하기 때문에 이때 answer를 카운트해주면 된다. 🛠 나의 코드 import sys input ..
[백준 알고리즘] 2178번 미로탐색, 파이썬(python)
[백준 알고리즘] 2178번 미로탐색, 파이썬(python)
2021.08.212178, 미로 탐색 📁 문제 출처 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 💡 생각 최소의 칸 수를 출력하기 위해서는 popleft를 한 뒤 4방향을 체크할 때 카운트 된 칸 수 +1로 라벨링 해주면서 끝까지 나아가면 최소 칸 수를 구할 수 있다. 🛠 나의 코드 from collections import deque n, m = map(int, input().split()) graph = [] for i in range(n): graph.append(list(map(int, input()))) dx = [0, 0, 1, -1] dy ..
[백준 알고리즘] 1926번 그림, 파이썬(python)
[백준 알고리즘] 1926번 그림, 파이썬(python)
2021.08.201926, 그림 📁 문제 출처 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 💡 생각 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하는 문제 모든 부분을 탐색해야 되기 때문에 BFS로 풀이 이어져 있는 부분은 count 변수로 카운트해주고 paint 배열에 append 그림의 개수는 len(paint), 가장 넓은 그림은 max(paint) 🛠 나의 코드 from collections import deque n, m = map(int, input().split()) graph = [] for i..
[백준 알고리즘] 1966번 프린터 큐, 파이썬(python)
[백준 알고리즘] 1966번 프린터 큐, 파이썬(python)
2021.08.141966, 프린터 큐 📁 문제 출처 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 💡 생각 숫자가 높을수록 중요도가 높다. 처음에 출구가 오른쪽인 줄 알고 deque 사용하면서 이것저것 하느라 삽질했다... index가 m인 정수가 몇 번째에 출력되는지 기억해야 되니까 index랑 value를 같이 저장하는 temp(배열)을 만들어주고 시작했다. 그리고 arr배열의 reverse 해줘서 중요도 배열을 정렬해줬다. 🛠 나의 코드 t = int(input()) for i in range(t): n, m = map(..
[백준 알고리즘] 2941번 크로아티아 알파벳, 파이썬(python)
[백준 알고리즘] 2941번 크로아티아 알파벳, 파이썬(python)
2021.08.142941, 크로아티아 알파벳 📁 문제 출처 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 💡 생각 처음에는 replace를 공백으로 해줬다가 다시 앞뒤가 크로아티아 알파벳으로 조합되어서 또 삭제가 되는 일이 있었다. 아예 *로 치환해줘서 카운트해줬다. 🛠 나의 코드 arr = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z='] n = input() total = len(n) cnt = 0 for i in range(len(arr)):..