developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 삼성코테기출자바풀이
  • 삼성코테자바풀이
  • 삼성코테자바꿀팁
  • Arima
  • 삼성코테파이썬
  • ARIMA모형
  • 삼성코테구현문제추천
  • SW역량테스트파이썬풀이
  • 삼성코테파이썬풀이
  • 백준파이썬풀이
  • 시계열
  • 삼성코테파이썬준비
  • 운영체제인터럽트
  • 삼성코테기출
  • 코테파이썬
  • MA모형
  • BOJ파이썬풀이
  • 통계학
  • AR모형
  • c++디자인패턴
  • 삼성코테구현풀이
  • 삼성코테준비
  • 데이터분석
  • 삼성코테자바준비
  • 카카오코테java풀이
  • SW역량테스트파이썬
  • 카카오코테
  • 통계분석
  • 시계열분석
  • c++ 빌더 패턴

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen
알고리즘/알고리즘문풀

BOJ - 치킨 배달 15686번 (python)

알고리즘/알고리즘문풀

BOJ - 치킨 배달 15686번 (python)

2021. 10. 16. 08:41

❓ 문제 - 백준 치킨 배달 15686번 - python 풀이법

출처 

(https://www.acmicpc.net/problem/15686)

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

 

📝 문제해결법

1. 이 문제는 BFS(조합)+구현으로 풀었다.

  • combination() 함수를 사용하여 기존에 있는 치킨 집에서 m개의 치킨집을 선택하여 해당 치킨집만을 운영했을 때 도시의 치킨 거리를 구하여 도시의 치킨 거리의 최솟값을 갱신해준다.
  • find_dist() 함수를 사용하여 현재 집 위치에서 선택된 치킨 집까지의 치킨 거리를 구하고 최소가 되는 치킨 거리를 찾아 도시의 치킨 거리로 합해준다. 또한 구한 도시의 치킨 거리와 min_value 변수를 비교하여 도시의 치킨 거리의 최솟값을 계속 갱신해준다.

 

 

💻 소스코드

n, m = map(int, input().split())
graph = []
chicken = []
home = []
for i in range(n):
    data = list(map(int, input().split()))
    for j in range(n):
        if data[j] == 2:
            chicken.append([i, j])
        elif data[j] == 1:
            home.append([i, j])

def combination(lst, num):
    result = []
    if num > len(lst):
        return result
    if num == 1:
        for i in lst:
            result.append([i])
    elif num > 1:
        for i in range(len(lst)-num+1):
            for temp in combination(lst[i+1:], num-1):
                result.append([lst[i]]+temp)
    return result

min_value = int(1e9)


def find_dis(c):
    global  min_value
    all_c = 0
    for h_x, h_y in home:
        min_c = 2*n+1
        for c_x, c_y in c:
            dist = (abs(h_x-c_x) + abs(h_y-c_y))
            min_c= min(min_c, dist)
        all_c += min_c
    min_value = min(min_value, all_c)


for c in combination(chicken, m):
    find_dis(c)

print(min_value)

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 아기 상어 16236번 (python)  (0) 2021.10.16
BOJ - 나무 재테크 16235번 (python)  (0) 2021.10.16
BOJ - 드래곤 커브 15685번 (python)  (0) 2021.10.16
BOJ - 사다리 조작 15684번 (python)  (0) 2021.10.15
BOJ - 감시 15683번 (python)  (0) 2021.10.15
  • ❓ 문제 - 백준 치킨 배달 15686번 - python 풀이법
  • 📝 문제해결법
  • 💻 소스코드
'알고리즘/알고리즘문풀' 카테고리의 다른 글
  • BOJ - 아기 상어 16236번 (python)
  • BOJ - 나무 재테크 16235번 (python)
  • BOJ - 드래곤 커브 15685번 (python)
  • BOJ - 사다리 조작 15684번 (python)
developer-ellen
developer-ellen

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.