본문 바로가기
728x90

알고리즘316

[Python] 백준 4963 섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 해결 움직일 수 있는 방향이 동서남북 대각선까지 총 8가지이다. 한 점을 잡고 갈수 있는 끝까지 가면서 Land를 Sea로 바꾸는 작업을 한다. 더이상 갈 수 없으면 다음 Land점을 잡고 똑같은 일을 한다. 이를 DFS로 코드를 만들 수 있다. 백준은 sys.setrecursionlimit()를 꼭 써야하는 것 같다. CODE import sys input = sys.stdin.rea.. 2023. 1. 22.
[python] 백준 11724 연결 요소의 개수 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 문제 해결 그래프가 몇개로 분리되어있는지 개수를 세는 문제 visited 리스트를 통해 지나간 점을 체크하면서 1번부터 n번까지 dfs나 bfs를 돌리면서 몇번 돌려야 visited 리스트 원소가 모두 True가 되는지 count 한다고 생각하면 된다. CODE(dfs) import sys sys.setrecursionlimit(500.. 2023. 1. 22.
[python] 백준 13023 ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 해결 bidirectical graph 가 4개가 연결되어있는 것이 하나라도 있으면 1을 출력하고 아니면 0을 출력 따라서 그래프가 이어지는 횟수가 4개가 되면 1을 출력하도록 하고 한번도 체크가 안되면 0을 출력하도록 하면 된다. visited 리스트를 만들어 방문했던 곳은 중복으로 방문하지 않도록 한다. CODE import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n)] .. 2023. 1. 22.
[python] 백준 14391 종이 조각 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 문제 해결 우선 비트마스크에 대해서 알아야 한다. 비트마스크는 숫자를 이진수로 배열함으로써 계산을 더 빠르게 할 수 있고 bool 연산도 빠르게 할 수 있다. (1은 True, 0은 False를 나타낸다.) 비트마스크의 연산은 크게 5가지가 있다. AND 연산 (&) (예시 : 11011 & 10001 = 10001) OR 연산(|) (예시 : 11001 & 10011 = 11011) XOR 연.. 2023. 1. 21.
728x90