파이썬 알고리즘 3주차 BFS : 특정 거리의 도시 찾기, 미로 탐색

1.개발 진행 및 완료상황

2주차 python algorithm bfs 문제 풀이 중
CSAPP 2주차 목표 읽기 완료
업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용
백준 18352

18352번: 특정 거리의 도시 찾기

문제 어떤 나라에는 1번부터 N 번까지의 도시와 M 개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X 로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K 인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X 에서 출발 도시 X 로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N =4, K =2, X =1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4…

www.acmicpc.net

풀이 과정 : 일반적으로 볼 수 있는 BFS문제였다.하지만 여전히 특정 값을 추출해 내는 과정을 어려워하는 내 입장에선 까다로웠다. 다음 도시로 탐색할때마다 특정 변수를 +1 해주는 것까진 설정할 수 있었으나, 그걸 적절한 과정에서 추출해 내는 것이 힘들었다. 꾸준한 연습이 필요하다.

정답 코드 :

import sys from collections import deque n,m,k,x = map(int,sys.stdin.readline().split()) graph= [[] for _ in range(n+1)] ans = [0](n+1) visited_bfs = [0](n+1) for _ in range(m): a,b = map(int,sys.stdin.readline().split()) graph[a].append(b) def bfs(x): data = [] queue = deque([x]) visited_bfs[x] = 1 ans[x] = 0 while queue: y = queue.popleft() for i in graph[y]: if visited_bfs[i] == 0: visited_bfs[i] = 1 queue.append(i) ans[i] = ans[y] + 1 if ans[i] == k: data.append(i) if len(data) == 0: print(-1) else: data.sort() for i in data: print(i, end=’\n’) bfs(x)

백준 2178

2178번: 미로 탐색

문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 …

www.acmicpc.net

풀이 과정 : 각각 경로마다 행,열의 값의 변화를 리스트로 만들었다. 따라서 동서남북으로 움직일 때마다 변화를 동일한 index 값을 리스트에 부여하는 방법으로 코드를 구성했다. 변화 결과 고려할 필요가 없는 곳으로 이동하는 경우를 조건문으로 제거했다.

정답 코드

import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) graph = [] for _ in range(n): graph.append(list(map(int, sys.stdin.readline().rstrip()))) def bfs(a, b): row_move = [1, 0, -1, 0] col_move = [0, -1, 0, 1] queue = deque() queue.append((a, b)) while queue: a, b = queue.popleft() for i in range(4): aa = a + row_move[i] bb = b + col_move[i] if aa > n-1 or aa < 0 or bb > m-1 or bb < 0: continue if graph[aa][bb] == 1: graph[aa][bb] = graph[a][b] + 1 queue.append([aa, bb]) return graph[n-1][m-1] ans = bfs(0, 0) print(ans)

새로 배운 내용

그래프의 이해

정의 : 실제 사물이나 현상을 정점(Vertex), 노드(Node), 간선(Edge)으로 표현하기 위해 사용 되는 컴퓨터 프로그래밍 개념

파이썬 알고리즘 3주차 BFS : 특정 거리의 도시 찾기, 미로 탐색

정글일지 16

CATALOG