buzz

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해설 지도 내에서 칸이 1이면 이동한다. 이동을 하면 그 전 칸의 이동한 값에 +1을 해준다. 코드 -파이썬 #백준 2178(미로 탐색) import sys input = sys.stdin.readline from collections import deque n, m = map(int, input().split()) graph = [] for i in range(n): graph.append([*map(int, str(in..

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 가장 기본적인 dfs/bfs 문제들은 visited 배열을 만들어서 방문 여부를 저장하는데 이 문제는 그 대신 부모 노드를 저장하면 된다. 그 외에는 다른 그래프 탐색 문제 풀 듯 풀면 된다. 코드 -파이썬 #백준 11725(트리의 부모 찾기) ##dfs 풀이 import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) n = int(input()) graph = [[] for _ in ..

문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 해설 이 문제는 좌표를 dx, dy에 저장하고 dfs 혹은 bfs로 풀면 된다. 좌표를 이용한 그래프 탐색 문제는 처음 풀어서 어떤 식으로 풀어야 하는지 당황스러웠는데 이런건 가장 이해하기 쉽게 푼 다른 사람 코드를 보고 외우는게 최고인 것 같다. 코드 -파이썬 #백준 4963(섬의 개수) # 1 : 땅, 0 : 바다 #dfs 풀이 import sys input = sys.stdin.r..

문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 해설 입력값을 받고 그래프를 생성하는 부분을 지나면 dfs 혹은 bfs로 문제를 풀어야 한다. dfs로 풀 때는 촌수를 cnt에 저장했다. 함수 한 번 씩 돌 때 마다 촌수가 1씩 올라간다. bfs로 풀 때는 deque를 이용하면 된다. 따로 촌수를 받을 필요는 없고 visited 변수에 현재 visited 값에 1촌을 더해서 저장해주면 된다. 처음 a를 1로 시작하는데 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 해설 DFS/BFS 문제는 항상 잘 못푸는데, 이 문제 역시 다른 코드를 보고 나서야 어떻게 풀어야 하는지 감을 잡았다.. 이 문제는 numbers 배열에 담긴 숫자들을 더하거나 / 빼서 target과 같은 값이 나오도록 만드는 방법의 수를 구하는 문제이다. 그럼 우선 더하기 / 빼기 밖에 없으니 직접 해보면 된다. numbers :..