[파이썬]코딩테스트 정리 블로그 [파이썬]코딩테스트 정리 블로그

아주 쉬운 문제다. 전형적인 3차원 배열을 이용하는 문제 z=0(벽을 부순 횟수) 으로 시작해서 삼차원 배열의 disit 배열을 채워주면 된다. *dist[z][x][y]= 벽을 z번 부셨을 때 (0,0)에서 (x,y)까지 가는 최단 거리 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import sys from collections import deque from itertools import combinations from typing import List, Lite..

역시 다국어가 적혀있는 문제는 전형적인 풀이법보다는 참신한 느낌이 강하다. 물론 웬만한 골드 문제는 전형적인 풀이법(개념) + ALPHA가 필요한 것 같다. 이 ALPHA 때문에 긴장해야하고 집중해야한다. 이 문제 역시도 ALPHA가 있는 문제였다. 지훈이와 불은 동 시간대에 같이 움직인다. 그러니 불 먼저 움직여야한다. 왜냐면 지훈이 먼저 이동 시키면 지훈이가 이동하고 지훈이가 이동한 곳에 불이 퍼지면 처치곤란이기 때문이다. 그래서 불 먼저 이동시키고 지훈이는 불이 퍼지지 않은 곳으로 이동시킨다. 그래서 시작할때 불 먼저 찾아서 큐에 집어넣고 그 다음에 지훈이 찾아서 큐에 집어 넣은 상태로 시작한다. ex)불(0초)->지훈(0초)->불(1초)->불(1초)->지훈(1초)->불(2초)->불(2초) 나는 코..

빙산을 녹일 때 주의해야할 점은 원래 빙산이었다가 녹아서 0이 된 점이 주변 빙산을 녹게하면 안된다는 점이다. 이것은 ch 혹은 visit배열로 해결 가능 그리고 처음에 두 덩이로 분리된다는 것이 무슨 뜻인지 해석이 안되어 힘들었다. 이것은 bfs로 지역 탐색했을 때 2 지역 이상 나오면 된다라고 해석하면 된다. 쉬워보이지만 구현할 때 잔실수도 많이 할 수 있어 주의해야한다. 얼음을 녹이고->시간 증가->bfs지역 탐색 순으로 반복하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 5..

벽의 위치를 3개 세우는 방식이 사람마다 다른 것 같다. 나는 from itertools import combinations을 이용하였다. 이차원 배열을 돌면서 벽의 위치를 수집하고 벽의 개수가 n개면 0~n-1까지의 리스트를 만들고 combinations(orders,3)로 3개의 조합을 뽑는 리스트를 생성 후 각각 벽을 세워줬다. 무언가 어려워보이지 않지만 실제로 풀다보면 굉장히 실수도 많이 발생하고 구현하기에 상당히 빡빡한 문제라는 생각이 들었다. 굉장히 탄탄한 벽 같다는 느낌을 받았다. 벽 위치 수집 -> combinations을 이용하여 각각 경우의 수마다 벽을 세우고->바이러스를 퍼트리고-> 모든 경우의 수 반복 후->안전영역 계산 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

출처:https://www.ioi-jp.org/joi/2011/2012-yo-prob_and_sol/2012-yo-t5/review/2012-yo-t5-review.html 육각형 관련한 탐색 문제 나오면 열2개,행1개 추가해서 배열을 확장하는 사고를 해야한다. 0에서 1과 접촉되면 갯수를 하나 추가해주면 된다. 중요한 것은 바깥쪽 1만 추가해줘야하니까 (0,0)에서 시작하여 0만 bfs 탐색해줘야한다. 풀이법을 알면 쉽고 모르면 굉장히 어렵게 느껴지는 문제 행 번호가 홀수일 때,짝수 일 때 왼쪽 아래,오른쪽 아래,왼쪽 위, 오른쪽 위가 다르다는 것이 까다로운 문제 보통 다국어가 쓰여있는 외국어 문제는 굉장히 참신하다는 느낌을 받는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..

삼차원 배열을 이용하는 전형적인 문제다. 아주 쉬운 문제 그램(2)을 발견하기전에는 z=0 이고 z가 0이면 벽을 못 뚫고 z=1이면 벽을 뚫을 수 있게 된다. dist[z][x][y]에서 z의 범위는 0에서 1까지 z가 0일 때는 그람 없이 x,y좌표에 도달하는 최소 거리 z가 1일 때는 그람을 발견하고 난 후 x,y 좌표에 도달하는 최소 거리 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 import sys from collections import deque from itertoo..

일단은 각 샘터의 위치를 큐에 집어 넣는다. 그리고 큐에서 꺼내서 +1,-1로 움직인다. 큐에 집어넣을때마다 갯수는 하나씩 추가하고 결과값도 누적으로 더해간다. bfs란 말에 맞게 너비우선탐색, 거리가 1,2,3,4 순차적으로 계산해간다. bfs의 정석 같은 문제라 생각 하지만, 이 문제에서 어려운 점은 메모리 초과 이것은 dict형으로 해결해주면 된다. dist 배열(내 코드에서는 vist)을 dict로 선언해주고 dist[nx]=dist[x]+1식으로 문제를 해결해가면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 i..

문제의 조건인데 1:[3] 2:[1] 3:[1] 4:[5] 5:[5] 6:[4] 7:[6] 이것을 그래프로 그려보면 1,3,5는 사이클을 이룸을 알 수 있다. 사이클을 이루는 원소들을 찾아내는 것이 문제 풀이 방법이란 것을 알 수 있다. 방향 그래프란 것도 낯설었고 문제의 조건을 보자마자 그래프를 이용한 사이클 문제라는 것을 떠올리는 것도 아직은 쉽지 않아 보인다. 문제 풀이 경험을 더 해야한다. 사이클을 찾는 방법은 기본적으로 dfs 탐색으로 각 정점을 방문하다가 이미 방문했던 정점을 또 방문하면 사이클을 형성하는 것이다. 16932 모양 만들기와 똑같은 문제다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..