728x90 반응형 Python169 2022.02.13 [백준] (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를 이용해서 각 정점의 방문 유무를 체크할 배열을 만들고, 이 문제에서 간선과 정점의 방향성은 없기 때문에 graph배열에 해당 정점의 인덱스에서 갈 수 있는 정점을 데이터로 넣어줍니다. 그 다음 for문을 돌려 check[i]가 0이면 방문하지 않은 곳이기 때문에 bfs함수를 실행시켜줍니다. 1 2 3 4 5.. 2022. 2. 13. 2022.02.13 [백준] (python 파이썬) 단지번호붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 bfs풀이 방식입니다. 2중 for문을 돌려 arr배열에 값이 1인 곳을 찾고 찾은 곳부터 bfs탐색을 합니다. bfs탐색이 끝나면 마을 1개가 생기게 됩니다. bfs함수를 돌때 deq에 데이터가 추가 될때마다 cnt를 1씩 더해줘서 한 마을의 총 집의 개수를 세주고 이 갯수를 ans배열에 담은 후, 모든 계산이 끝난 후 배열을 sort로 정렬하여 출력합니다. 1 2 3 4 5 6 7 8 9 .. 2022. 2. 13. 2022.02.12 [백준] (python 파이썬) 그림 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 이 문제를 처음 풀 때, 입력 받은 값을 저장 한 arr 배열과 해당 인덱스에 방문유무를 체크하기 위한 arr과 같은 크기의 배열을 만들고 방문할 때마다 해당 인덱스의 값을 1로 바꾸어 주면서 코드를 작성했다. 그러니 메모리 초과가 발생하여 arr배열만으로 문제를 해결했다. arr의 값이 1일 때 bfs함수를 호출하고 arr값을 0으로 바꾸어 주면서 방문유무를 체크했다. 1 2 3 4 5 6 7 .. 2022. 2. 12. 2022.02.12 [백준] (python 파이썬) 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 from collections import deque # 익은 토마토가 주변의 토마토를 익게 할 수 있는 위치.. 2022. 2. 12. 이전 1 ··· 33 34 35 36 37 38 39 ··· 43 다음 728x90 반응형
