본문 바로가기

💻 Programming/알고리즘 테스트17

[python] 백준18352_특정 거리의 도시 찾기 (DFS&BFS) 문제 풀이 '모든 도로의 거리는 1'이라는 조건 덕분에 BFS를 이용하여 해결할 수 있다. 코드 from collections import deque n,m,k,x = map(int,input().split()) # 도시 개수, 도로 개수, 거리 정보, 출발 도시 번호 graph = [[] for _ in range(n+1)] # 도시 개수 만큼 graph 리스트 생성 for _ in range(m): # 도로 정보 입력받아서 graph 에 정장 a, b = map(int,input().split()) graph[a].append(b) distance = [-1]*(n+1) # 모든 거리는 -1 로 초기화 distance[x] = 0 # 출발 도시 거리는 0 q = deque([x]) # 출발 도시를 큐.. 2022. 2. 6.

[python] 백준14502_연구소 (DFS&BFS) 문제 풀이 DFS로 바이러스 퍼지게 하는 함수와 현재 맵에서 안전영역을 구하는 함수를 만들어 두고, 빈 공간에 울타리를 치는 모든 경우의 수를 DFS로 찾으면서 매번 안전영역의 크기를 검사한다. 코드 n, m = map(int,input().split()) data = [] # 초기 맵 리스트 temp = [[0]*m for _ in range(n)] for _ in range(n): data.append(list(map(int,input().split()))) # 서남동북 dx = [-1,0,1,0] dy = [0,1,0,-1] result = 0 # DFS로 바이러스 퍼지게 하기 def virus(x,y): for i in range(4): nx = x + dx[i] ny = y + dy[i] # 상.. 2022. 2. 6.

[프로그래머스] '파이썬을 파이썬답게' 강의 정리 프로그래머스 '파이썬을 파이썬답게' 강의 정리 https://programmers.co.kr/learn/courses/4008 파이썬을 파이썬답게 본 강의는 파이썬 문법을 이미 알고 있는 분들을 대상으로 만들어졌습니다. ##### 이런 분들께 추천합니다 * 파이썬 문법을 알고 계시는 분 * 알고리즘 문제를 조금 더 쉽게 풀고 싶은 분 * Python 코 programmers.co.kr 1. 몫과 나머지 : divmod() 함수 사용 # 다른 언어 a = 7 b = 5 print(a//b, a%b) # 파이썬 a = 7 b = 5 print(*divmod(a,b)) 2. n진법으로 표기된 string 을 10진법 숫자로 변환하기 # 파이썬 # base(5)진법으로 표기된 num(3212)를 10진법으로 변.. 2021. 8. 3.

[BFS] 미로 탈출 - 문제 주인공은 NxM 크기의 직사각형 형태의 미로에 갇혀 있다. 주인공의 위치는 (1,1) 이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0 없는 부분은 1로 표시되어 있다. 이 때 주인공이 탈출하기 위해 움직여야하는 최소 칸의 개수를 구하시오. 단 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. - 해설 BSF로 풀 수 있는 문제. BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다. 그러므로 (1,1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다. from collections import deque n,m = map(int, input().split()) # 2차.. 2021. 5. 17.

[DFS] 음료수 얼려 먹기 - 문제 NxM 크기의 얼음 틀이 있고 구멍이 뚫려 있는 부분을 0, 칸막이가 존재하는 부분을 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상하좌우로 붙어있는 경우 서로 연결된 것으로 간주한다. 이 때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. ex) 00110 00011 11111 00000 -> 아이스크림 3개 생성 - 해설 DFS 로 해결할 수 있는 문제 1. 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 0 이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문 2. 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 다시 진행하면 연결된 모든 지점을 방문할 수 있다. 3. 1~2번의 과정을 모든 노드에 반복하며 방문하지 않은 .. 2021. 5. 17.

이전 1 2 3 다음

티스토리툴바