DFS 2

[백준] 19236. 청소년상어 - python

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 삼성SW 역량테스트 기출문제 문제풀이 시뮬레이션 + 완전 탐색(dfs) 물고기이동 번호가 작은 물고기부터 이동 (1~) 이동가능한 칸 빈칸 다른 물고기가 있는 칸 이동할 수 없는 칸 상어가 있는 칸 공간의 경계를 넘는 칸 (맵을 넘어선 칸) 이동할 수 없으면 45도 반시계 회전하고 이동(8방향 모두 확인) 회전을 해도 이동할 칸이 없으면 이동하지 않음 이동시 다른 물고기가 있으면..

알고리즘/백준 2020.07.15

[SWEA] 1949. 등산로 조성 (python)

문제풀이 dfs를 이용하여 최적화를 하는 문제이다. 가장 높은 봉우리에서 부터 탐색을 시작함. 봉우리의 사방을 탐색 다음 길이 낮으면 그대로 탐색 진행(dfs호출) 다음 길의 높이가 같거나 높고 공사를 아직 안했으면 공사를 진행함 공사는 최대 깊이 K만큼 할 수 있음 (1~K) 모든 경우( 모든 공사깊이 ) 를 탐색 공사 후에 다음 길의 높이가 낮아졌다면 dfs를 호출해서 탐색 계속 (dfs호출) 등산로길이의 최대값을 계속 업데이트해서 최대값을 결과로 얻음 소스코드(python) dr = [-1,0,1,0] dc = [0,1,0,-1] def dfs(r,c,path,isConst): global ans if ans < path: #최장 등산로 갱신하기 ans = path #사방 탐색 : 등산로 탐색 fo..

알고리즘/SWEA 2020.07.08