몽상실현개발주의

[BOJ] 11725 / 트리의 부모 찾기 / Python 파이썬 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 각 node의 root를 찾는 문제이다. 최상단의 root 노드가 항상 1로 시작하기 때문에, 모든 edge 를 기록한뒤 1부터 Tree 를 내려가며 root 를 기록하였다. from collections import deque N = int(input()) graph = [[] for _ in range(N+1)] for _ in range(N-1): f, t = map(int, inpu..

[자료구조] 그래프 Graph 그래프 Graph 정점 (vertex / node) , 간선 (edge / link) 로 이루어진 자료구조 정점과 간선은 집합이기 때문에 중복된 값을 가지지 않는다. 그래프는 꼭 연결되어 있을 필요도 없고, 간선이 반드시 서로 다른 두 정점을 연결해야 할 필요도 없다. 비선형 자료구조이다. 즉, 선형 자료구조와 다르게 하나의 원소 다음에 여러개의 원소가 올 수 있다. (1:M , 0 외부에서 오는 간선 수 진출 차수(out-degree) : 해당 정점을 시작으로 하는 간선의 수 (=외차수) => 외부로 나가는 간선 수 루프(loop) : 간선 하나에 동일 노드가 연결(부속)되어 있는 경우 경로(path) : 간선을 따라 갈 수 있는 길. 정점의 나열로 표시 ex) , , ...

[BOJ] 2146 / 다리 만들기 / Python 파이썬 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 주어진 이중배열에서 1로 이루어진 무리 사이의 최단 거리를 구하는 문제이다. 문제를 이해하였지만, 구현하는데에 많은 어려움이 있었다. BFS 를 이용하여 최단거리를 구하는 것과 문제를 풀기위한 환경 구성을 함께 고려해 주어야 한다. from collections import deque def setIsland(y, x, setN): glo..

[BOJ] 2178 / 미로 탐색 / Python 파이썬 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 경로탐색의 기본 문제이다. bfs 로 경로상의 이동 거리를 저장하며 경로를 진행하도록 하였다. from collections import deque N, M = map(int, input().split()) maps = [] for _ in range(N): maps.append(list(map(int, list(input())))) dq = deque() dq.ap..

[BOJ] 7576 / 토마토 / Python 파이썬 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 이차원 배열에서 주어진 시작점으로 부터 주어진 규칙을 시행하는 문제였다. 처음에는 각각의 시작점에서 시행하는 경우가 동시에 발생 하는 것을 고려하지 못하고, 독립적으로 시행하게 구현하였더니 시간초과가 발생하였다. BFS 로 각각의 시작점을 같은 단계에서 동시에 수행되도록 구현하였더니 통과하였다. from collection..

[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..