ayeongjin 님의 블로그

https://www.acmicpc.net/problem/16946 ✅ 문제 조건1. 0 : 이동 가능, 1 : 이동 불가능 (벽)2. 벽을 부수고 이동할 수 있는 곳으로 변경3. 그 위치에서 이동할 수 있는 칸의 개수 세기 정리하면 벽이 나타날때마다 그 벽을 포함해서 연결된 빈공간의 크기를 구하면 된다 ✅ 접근 방법 방법 1)각각의 칸마다 bfs 실행 -> 시간초과 O((N * M) * (N * M)) = O((N*M)^2)전부 다 조건대로 구하면 되지만 그렇게 풀이하면 시간초과 난다. 방법 2)1. 처음에 한번의 bfs 전체 순회하며 각 칸의 크기 측정 (2667번 단지번호 붙이기 문제처럼 각 방의 고유번호를 측정, 고유번호는 0부터 시작)2. 방의 고유번호를 다 붙였으면 그 붙인 크기를 리스..

https://www.acmicpc.net/problem/1726 ✅ 문제 조건 1. 전진 명령 : 1~3칸 전진 가능2. 회전 명령 : 오른쪽 또는 왼쪽으로 90도 회전 가능3. 시작위치와 시작방향, 도착 위치와 도착 방향이 주어진다4. 몇번의 명령으로 도착지점에 도착할 수 있는지 출력 ✅ 접근 방법일단 방향까지 필요한 문제이기 때문에 [세로][가로][방향]을 가지는 3차원 visited 배열을 만들어야한다.그리고 1. 전진 명령을 할 경우와 2. 회전 명령을 할 경우를 나눠서 명령시행을 반복한다.최종 도착과 맞는 위치와 방향일 경우 break ✅ 구현 1. 전진 명령# 전진for k in range(1, 4): nr, nc = cr + direction[cd][0] * k, cc + dir..

https://www.acmicpc.net/problem/17472 ✅ 문제 조건1. 다리의 방향은 가로 또는 세로로만 연결 가능하다2. 방향이 가로인 다리는 다리의 양 끝이 가로방향으로 섬과 인접, 세로도 마찬가지3. 다리의 길이는 2 이상4. 다리 교차 가능5. 모든 섬이 연결하는 다리 길이의 최솟값 구하기 ✅ 접근 방법 1. 섬 위치 체크BFS를 이용해 하나의 섬마다 고유 번호를 부여하고, 바다와 맞닿아 있는 가장자리 좌표를 따로 저장했다.여기까지는 다리만들기1이랑 거의 비슷하게 풀었다. 2. 섬의 가장자리만 모아둔 배열에서 다른 섬까지 한 방향으로 다리 만들어 나가기가장자리 좌표에서 상하좌우 한 방향으로 쭉 탐색하고, 다른 섬에 도달 가능한 경우 다리 후보로 저장한다.이때 다리 길이가 2 이상을..

https://www.acmicpc.net/problem/13460 ✅ 문제 조건 1. 보드 상하좌우로 욺직여서 구슬 이동2, 빨간구슬만 빼내기3. 각 단계마다 네방향으로 기울이며 두 구슬을 동시에 이동3-1. 파란구슬이 구멍에 빠지면 실패3-2. 빨간구슬이 구멍에 빠지면 성공4. 10회 반복 후, 성공 못하면 -1 ✅ 접근 방법 # 문제 1먼저 상하좌우로 이동하며 그때마다 턴을 반복해야한다는 건 이해했지만, 두 개의 구슬이 같은 위치에 겹치면 어떻게 처리해야할지 생각하는 데 오래걸렸다.그래서 구슬의 위치와 현재 방향을 바탕으로 어떤 구슬이 먼저 움직어야하는지 계산할까 생각했지만 너무 복잡해서 포기했다.위의 방법을 고민하던 중, 어떤 구슬이 먼저 움직어야하는지 계산을 하지 말고 일단 그냥 두 개의 구슬..

https://www.acmicpc.net/problem/17822 매 T 마다 반복되는 동작은1. 원판 회전2-1. 인접한 값 중 서로 같은 값이 있으면 그 값들 삭제2-2. 인접하면서 같은 수가 없는 경우에는 원판 수의 합보다 작은 수는 += 1, 큰 수는 -= 1 그래서 세가지 함수를 만들었다.  1. 원판 회전def turn(x, d, k): # x의 배수인 원판을 d(0: 시계, 1: 반시계) 방향으로 k칸 회전 for i in range(x, N+1, x): if d == 0: # 시계 방향 circles[i-1] = circles[i-1][-k:] + circles[i-1][:-k] else: # 반시계 방향 circ..

https://www.acmicpc.net/problem/19238 처음에는 모든 출발지와 도착치의 좌표가 겹치는 경우가 없다고 생각해서 출발지와 목적지를 전부 mp에 대입해버렸다.그리고 택시의 처음 위치부터 시작해서 너비우선탐색으로 가장 가까운 출발지점을 찾고, 해당 번호의 도착지를 찾은 후, 연료와 택시 위치를 갱신해서 풀었다.그렇게 해서 1퍼센트에서 틀렸습니다 떴다. # 실패 코드 1'''현재 위치에서 가장 가까운 손님에게 가기 (거리가 같을 경우 행번호 -> 열번호 순서로 탐색)현재 택시와 같은 위치라면 거리 = 0한칸 이동마다 연료 1 소모목적지 도착시 승객 이동 중 소모한 연료의 두배 충전이동중 연료 바닥나면 영업 종료 (도착과 동시에 연료 바닥날시에는 이동 성공)'''from collecti..

https://www.acmicpc.net/problem/2638 백준 2637 빙산 문제 처럼 몇번 닿았는지 카운트하고 조건에 만족했을 때 (2번 이상 닿았을때) 치즈를 녹이는 과정을 반복하려고 했다.  1. 무조건 외부 공기인 (0, 0)부터 덱에 넣어 외부 공기 탐색하며 외부 공기 표시(-1) 하기2. 외부 공기 탐색 도중 치즈 (1)이 나오면 해당 구역 visited에 += 13. bfs 전부 탐색 후, visited가 2 이상인 부분 (외부공기가 두번 이상 닿은 부분) 치즈 녹이기4. 치즈가 전부 녹을 때 까지 (녹이는 치즈가 없을 때 까지) 반복 # 성공 코드 1# python 34976 KB 1176 msfrom collections import dequeN, M = map(int, inpu..

https://www.acmicpc.net/problem/13913 메모리나 시간초과 생각 안하고 바로 q에 이동 경로를 함께 append하면서 bfs로 풀었는데 시간초과 났다. 어쩐지 이게 왜 골드일까 생각했어야했다. # 실패 코드 1from collections import dequeN, K = map(int, input().split())q = deque([(0, N, [N])])visited = [False] * 100001visited[N] = Truewhile q: ct, cc, c_lst = q.popleft() if cc == K: print(ct) print(*c_lst) break for nc in [cc-1, cc+1, cc*2]:..

https://www.acmicpc.net/problem/12851 숨바꼭질 3 문제는 이동 방법마다 초가 달라서 힙큐로 풀었는데 이 문제는 가중치가 같아서 덱으로 풀었다.가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 문제가 해결하기 어려웠다.visited 를 True / False로만 나눠서 풀면 해당 위치까지 몇가지의 수로 방문할 수 있는지 확인할 수 없었다. 일단 visited 배열을 만들고 -1로 초기화 한 후, 수빈이의 처음 위치 visited[N] 은 0초로 초기화했다.visited[i] : i 위치에 도달하는데 최소 몇초가 걸리는지그리고 bfs 탐색을 위한 queue 배열도 선언하고 (N까지 몇초에 왔는지, 위치N) 으로 시작했다.q = deque([(0, N)])bfs를 실행하면서 ..

https://www.acmicpc.net/problem/2573  처음엔 전체 배열을 N * M으로 다 탐색하면서 빙하의 녹는 부분을 갱신하려고 하니 파이썬으로 시간초과가 났다. 1. 빙산 다 녹을 때 까지 while2. 전체 N * M 배열 탐색하면서 바닷물인 경우에 그 주위를 보면서 빙산이 있는 경우 빙산 -= 1 녹이기3. 녹인 후 전체 배열 return4. 전체 N * M 배열 탐색하면서 빙산 덩어리 세기5. 다 센 후 덩어리 return6. 덩어리 2개 이상 나올때, 아니면 다 녹았을 때 (0개) 일 때 결과 갱신하고 break # 실패 코드# python 시간초과# pypy 1668 ms, 215748 KBfrom collections import dequeN, M = map(int, inp..