문제로이동 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com (상) DFS, (하) BFS 문제 설명 이 문제는 DFS, BFS로 풀이가 가능하며, 최단경로를 구하는 문제이므로 다익스트라 접근도 가능합니다. 저는 DFS와 BFS로 접근했으며 아래와 같은 변수를 사용했습니다. 1. 방문을 체크하는 visited 2. Cost를 저장하는 dp 3. 기본 필드 입력 field 난이도 D3정도 되는 일반적인 BFS, DFS문제와 비교했을때 가장 큰 차이점은 가지치기 입니다. 그렇기에 아직 방문하지 않았거나(visited) 현재 좌표에서 cost가 더 낮다면 갱신(dp)하는 방법으로 가지치기 할 수 있습니다. 아래는 co..

문제로이동 목차 문제 설명 일반적인 최소스패닝 트리(MST) 문제입니다. 크루스칼 알고리즘과 프림 알고리즘으로 해결해봤습니다. 런타임 에러1 이 문제는 테스트 케이스가 여러개 들어옵니다. 마지막 0 0 입력이 왜 있는가 했더니,, 결국 이 문제점을 뒤늦게 이해하고 코드 수정을 하여 AC를 받았습니다. 즉, 0 0이 입력되기 전까지 테스트 케이스가 무한대로 들어오니 M,N 값을 검증해야 합니다. if(M==0 && N==0) return; 런타임 에러2 전혀 생각지 못했던 이유였습니다. 하단 소스코드엔 while문 밖으로 선언되어 있지만 아래처럼 while문 내에 삽입했더니 발생했습니다. while(true){ BufferedReader br = new BufferedReader(new InputStrea..

문제로이동 목차 문제 설명 펜윅트리를 하며 비트마스킹을 써왔던 것이 조금은 도움이 되었습니다. 이번 문제는 만들어둔 사진으로 대체하겠습니다. 아래의 과정(BFS)을 반복적으로 거치고 나면 가장 처음에 입력된 값을 기준으로 1의 거리를 가진 간선들이 연결되어 있습니다. 소스 코드 Python from collections import deque import sys input = sys.stdin.readline MIN = -10e9 N = int(input()) M = int(input()) arr = [MIN]*1000001 dq = deque() xs = list(map(int,input().split())) for x in xs: arr[x] = 0 dq.append(x) maxnum = 0 whil..

문제로이동 목차 문제 설명 재귀함수를 이용해 풀었습니다. 각 order의 특징을 살펴보면 inOrder : LVR (왼쪽-뿌리-오른쪽) postOrder : LRV (왼쪽-오른쪽-뿌리) preOrder : VLR (뿌리-왼쪽-오른쪽) 이러한 특징을 가졌는데, inOrder와 postOrder를 잘 보시면 구조가 다르기 때문에 이를 이용하여 풀어야 합니다. 1. postOrder는 뿌리의 위치가 항상 맨뒤에 존재합니다. 그래서 매 번 가장 마지막 노드를 가장 먼저 출력합니다. 2. 해당 뿌리 위치 왼쪽까지를 재귀합니다. 3. 해당 뿌리 위치 오른쪽부터 재귀합니다. 4. 1~3을 반복합니다. 문제 후기 pypy3와 python3의 차이점을 몸소 경험했던 문제였습니다. 신선한 충격이었고 덕분에 멘탈이 탈탈 털..

문제로이동 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 목차 풀이 과정 첫 시도엔 BFS를 떠올려 시도했습니다. D3에 BFS가 나올리는 없어서 다시 생각해보니 다이아몬드 형태를 한 번에 더할 수 있겠다는 확신이 들었습니다. 0 - 1 - 2 - 1 - 0과 같이 점차 증가했다가 중간값에 도달하면 다시 감소하는 식을 구했습니다만, 해당 방법 이외에도 양 끝점에서 동시에 값을 더하는 방법이 있습니다. for(int i =0;iN/2)break; Deque orderQ = new ArrayDeque(); for(Pos dpos:direction) { int nx = tmp.x+dpos.x; int ny = tm..

문제로이동 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 목차 문제 설명 8*8 크기의 체스판을 완전탐색합니다. 즉, 크기가 8*8보다 더 큰 경우 위치를 옮겨가며 확인해야 합니다. 왼쪽부터 오른쪽으로 스캔하듯 모두 훑어줍니다. 가로 탐색이 끝났다면 이제 세로축을 한 칸 증가시켜야겠죠? 한 칸 내린후 위와 동일하게 오른쪽으로 쭉 가야합니다. 어떤 로직인지 이해 하셨나요? 그럼 최종적으로 아래 그림처럼 탐색을 마칩니다. 자. 이제 위와같은 체스판이 아닌 흑백이 섞인(또는 뒤죽박죽) 체스판 모양이 입력됩..