Algorithm/Graph188 [파이썬] 백준 1388 : 바닥장식 (실버4) [파이썬] 백준 1388 : 바닥장식 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 문제 풀이 0. 접근 방식 연결 요소의 개수를 찾는 문제이다. 기존 2차원 배열과 다르게 가로연결, 세로로 연결된 블록들이 하나로 취급되고 가로블록과 세로블록이 나누어져 있어서 별도의 처리가 필요하다. 배열의 크기가 작아서 BFS와 DFS의 차이가 크지 않다. DFS가 더 편하니 DFS로 구현 1. 입력 받기 N,M = map(int,input().split()) arr = [] for i in range(N): arr.append.. 2023. 5. 9. [파이썬] 백준 2667 : 단지번호 붙이기 (실버1) [파이썬] 백준 2667 : 단지번호 붙이기 (실버1) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 0. 방향성 생각 2차원 배열의 탐색이고 군집의 크기와 개수를 탐색하는 문제이다. 주어진 배열의 길이가 충분히 짧아서 DFS로도 나쁘지 않은 성능을 낼 수 있을 것 같다. 1. 입력 받기 import sys sys.setrecursionlimit(10**6) N = int(input()) apt = [] for i in range(N): s = list(input()) apt.append(s) 배열.. 2023. 5. 8. [파이썬] 백준 1012 : 유기농 배추 (실버2) 백준 1012 : 유기농 배추 (실버2) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 풀이 0. 방향성 생각 군집의 개수를 측정하는 문제이므로 DFS로 접근해야함을 알 수 있다. 밭의 크기가 크지는 않지만 재귀적으로 DFS를 구현하면 오류가 발생할 수 있으므로 재귀 리미트를 설정한다. 1. DFS 함수 정의 import sys sys.setrecursionlimit(10**6) def dfs(x,y): if x=M : return 0 if land[x][y] == True : land[x][y] = False r.. 2023. 5. 8. [파이썬] 백준 14940 : 쉬운 최단거리 (실버1) 백준 14940 : 쉬운 최단거리 (실버1) 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제 풀이 0. 방향성 생각 최단 거리를 요구하는 문제이기 때문에 BFS로 접근해야함을 알 수 있다. 또한 배열의 크기가 1000x1000이기 때문에 재귀를 통한 DFS 구현 시 시간이 오래 소요됨을 유추할 수 있다. 1. 입력 받기 import sys from collections import deque h,w = map(int,sys.stdin.readline().spli.. 2023. 5. 7. 이전 1 ··· 44 45 46 47 다음
