http://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net # 조건 정점의 개수 N N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우 i에서 j로 가는 간선이 존재한다는 뜻 총 N개의 줄에 걸쳐 문제의 정답을 인접행렬 형식으로 출력 # 접근 방법 및 Solution 모든 그래프에 대한 정점을 받은 후 결과를 저장해줄 배열 만들기 이후 bfs를 이용하여 접근 가능한 정점 들을 기록해준다. 전형적인 bfs 문제로서 순회가 가능한 것을 체크하기 위하여 시작 지점에 1을 해..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net # 조건 정사각형 모양의 지도가 있다. 1은 집이 있는 곳, 0은 집이 없는 곳 연결된 집의 모임의 단지를 정의하는데, 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다 총 단지수를 출력하고 각 단지에 속하는 집의 수를 오름차순으로 출력하라. # 접근 방법 및 solution 델타 함수를 이용한 dfs를 이용하여 연결된 단지를 체크해준다. 방문한 집들의 값을 0으로 변..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net # 조건 NxM 크기의 배열로 표현되는 미로 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸 (1,1) 에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸 수를 출력 # 접근 방법 BFS를 통하여 탐색을 진행한다. Queue에 넣어주며 방문기록을 현재 좌표+1로 해준다. 간선의 가중치가 모두 같은 그래프로 생각할 수 있기 때문에 bfs를 이용한다면 최단 경로를 바로 구할 수 있다. import sys sys.s..

https://www.acmicpc.net/problem/11724 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 # 조건 방향 없는 그래프가 주어질 때, 연결 요소의 개수를 구하라 1

https://www.acmicpc.net/problem/1697 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net # 조건 수빈이는 현재 점 N(0= k: return n - k elif k == 1: return 1 # 홀수인경우 도착지점+1, 도착지점 -1만 탐색하며 +1 해준다. elif k % 2: return min (find(n, k + 1), find(n, k - 1)) +1 # 짝수인 경우 시작점-도착점, k//2+1 중 최소값으로 갱신해준다. # 또한 k//2 로 이동하여 출발점까지 고고 e..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net # 조건 모든 사람들은 최대 6단계 이내로 서로 아는 사람으로 연결 케빈 베이컨 게임은 임의의 두사람이 최소 몇 단계 만에 이어질 수 있는지 계산 유저의 수 N(0

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 N x N 모양의 지역에 디저트 카페가 모여있다. 칸의 숫자는 디저트의 종류를 뜻하며 카페들 사이에는 대각선 방향으로만 이동 가능 대각선으로 카페 투어를 떠난 후 다시 처음 카페로 돌아오면 된다. 이때, 한 번 먹은 종류의 디저트 카페는 갈 수 없고, 왔던 길도 돌아갈 수 없다. # 접근 방법 #1 dfs dfs를 이용하여 사각형을 그려주며 탐색할 수 있다. 회전 방향을 정하고, 카페와 디..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 a-> b와 같은 순서로 비상연락망과 연락을 시작하는 당번에 대한 정보가 주어진다. 한 번에 여러 명에게 연락이 가능할 때 연락을 받을 수 있는 사람 중 가장 마지막에 받은 사람의 번호를 출력하라 이 때, 가장 마지막에 받은 사람이 여러 명이라면 제일 큰 번호 출력 # 접근 방법 bfs를 이용하여 연락가능한 사람들을 큐에 넣어준다. 이후 큐에 있는 번호를 pop해주며 연락 사이클을 돌려주는..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net # 조건 - 트리에서 리프노드란, 자식의 개수가 0인 노드 - 트리가 주어질 때, 노드 하나를 지울 것인데, 그 때 남은 트리에서 리프 노드의 개수를 구하여라 # 접근 방법 - 노드 하나를 지웠다면 아래 자식 노드들 또한 함께 지워지는 것이 규칙 - 따라서 지워지는 노드 기준, 아래로 연결되어 있는 노드들을 -2로 변경해준다. - -2인 경우는 나올 수 없는 수 이기도 하며 False로 설정..