영

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 문제해결 양방향 연결노드에 대한 정보가 주어지고 노드 a에서 b까지의 거리를 구하는 문제 방문처리는 1차원 배열로 가능하지만 a~b 까지 도달하는 각 거리를 저장하기 위해서 graph는 2차원으로 처리하였다. 완전탐색으로 dfs, bfs 둘중 한방법을 선택해도 되지만, 한 점에서 목표지점까지를 방문함에 있어서 거리를 파라미터로 넘기고싶어 dfs로 처리하였다. import sys def input(): return sys.stdin.readli..

자료구조 알고리즘/백준 2022. 8. 28. 21:10

https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 문제 해결 문제 : 1이 들어있는 칸을 연결한 것을 모양이라 부른다. 배열 칸 하나의 수를 변경해서 만들 수 있는 모양의 최대 크기를 구하자 1을 변경하면 모양에 변화가 없으니 0을 변화시켜야 함을 알 수 있다. 배열의 한 칸의 수를 변경하여 만들 수 있는 모양의 최대 크기에서 0의 칸을 하나 변경시켜 인접한(상하좌우) 곳을 살펴서 서로 다른 영역의 크기의 합 + 1(현재칸)의 최댓값을..

자료구조 알고리즘/백준 2022. 8. 26. 22:51