몽상실현개발주의

[BOJ] 4963 / 섬의 개수 / Python 파이썬 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 주어진 이차원 배열에서 상하좌우 그리고 대각선으로 이어진 그룹의 개수를 구하는 문제이다. 인접한 섬을 찾는 방법은 이차원 배열에서의 기본 탐색 방법을 사용하였고 (dy, dx) Queue 를 사용한 BFS 로 경로를 저장하여 탐색하였다. import sys from collections import deque input = sys..

[BOJ] 2667 / 단지번호붙이기 / Python 파이썬 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 이중배열로 된 데이터를 탐색하는 문제이다. 붙어있는 block 의 개수를 구하기 위하여, deque 로 BFS 를 구현하여 탐색하였다. import sys from collections import deque input = sys.stdin.readline def BFS(r, c): dq = deque() dq.append((r, c..

[BOJ] 9466 / 텀 프로젝트 / Python 파이썬 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 순환되는 graph 를 찾는 문제이다. 키 포인트는 마지막 node 와 첫 node 가 이어져서 Loop 를 이룬다는 것이다. 순환되는 graph 를 찾는 방법은 다음과 같다 방문 node 를 check 하며 순회 거쳐간 node 를 재방문 하였을때 순회 종료 마지막 node 와 이어진 node 의 index 부터 grpah 를 구성 lo..

[BOJ] 2331 / 반복수열 / Python 파이썬 https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 풀이 제시되는 규칙으로 수열을 만들고, 반복되지 않는 수의 개수를 출력하는 문제이다. 각 수의 자리수인 0~9 까지의 수를 거듭제곱한 합으로 수열이 형성되므로, 수열은 반복되는 구간이 만들어진다. 이를 이용하여 수의 중복을 확인하고 중복 이전까지의 수열의 길이를 세어주었다. A, P = map(int, input().split()) nums = [A] while True: tmp = 0 for s in str(nums[-1]): tmp += int(s)..

[BOJ] 10451 / 순열 사이클 / Python 파이썬 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 풀이 순열과 index 로 그려진 graph 의 사이클 수를 구하는 문제이다. 순열의 수가 다음 순열의 index 가 된다는 것을 이해하면 쉽게 구할 수 있다. import sys input = sys.stdin.readline T = int(input()) for..

[BOJ] 1707 / 이분 그래프 / Python 파이썬 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 풀이 이분 그래프 (Bipartite Graph) 를 판별하는 문제이다. 그래프를 탐색하면서 node 에 -1 을 곱해주는 것으로 이분 그래프를 검사하였다. import sys input = sys.stdin.readline T = int(input()) for _ in range(T): N = int(input()) nums..

[BOJ] 11724 / 연결 요소의 개수 / Python 파이썬 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 풀이 그래프를 구성하는 노드와 엣지를 입력받아, 연결되어 있는 그래프의 수를 구하는 문제이다. BFS 로 그래프의 구성을 확인하였고, BFS 는 queue 로 구현하였다. import sys def countGraph(N, graph): if N == 1: return ..

[BOJ] 1260 / DFS와 BFS / Python 파이썬 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 DFS 와 BFS 탐색을 시행하여 출력하는 문제이다. DFS 는 재귀로, BFS 는 queue 로 구현하였다. def DFS(V, N, maps): global DFSvisited DFSvisited.append(V) for i in range(1, N+1): if maps[V][i] and ..