'🥇코딩테스트:Algorithm' 카테고리의 글 목록 (3 Page)

visited배열이 3차원인 bfs 최단경로 탐색 문제 (백준 1600번)

2024.02.28

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이를 위한 핵심 말 이동 횟수에 따른 방문처리를 해줘야 합니다. 보통 방문체크를 visited[][] 와 같이 2차원 배열로 진행하지만, 이렇게 하게되면 말로 이동한 지점에 visited가 true로 되어 그냥 이동이 더 이상 진행하지 못하는 경우가 생길 수 있습니다. 예를들어 (0,0)에서 bfs를 수행하면 (0,1) (1,0) (1,2)가 방문체크 되고 큐에 들어갑니다. 여기..

🥇코딩테스트:Algorithm

이분 그래프 (백준 1707)

2024.02.22

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분그래프 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 풀이를 위한 아이디어 : 이분그래프의 하나의 간선에 연결된 두 노드의 색상은 서로 달라야 한다. 모든 노드에 대해 bfs를 수행하면서 연결된 노드와 서로 색상이 다른지 확인해야 한다. 변수 방문처리와 색상확인을 동시에 수행하는 int[] chk 배열을 뒀다. -1 : 아직 방문하지 않은 노드 ..

🥇코딩테스트:Algorithm

DFS + DP (백준 1520 내리막길)

2024.02.20

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이과정 (r,c)에서 목적지 (M-1,N-1)까지 갈 수 있는 모든 경로의 갯수는 (r,c)와 인접한 (nr,nc)에서 목적지 (M-1,N-1)까지 갈 수 있는 경로 갯수의 합이다. 위 과정을 그림으로 나타내면 아래와 같다 보통의 bottom-up 방식으로 구현하는 dp가 아니었다. 메모리제이션 방법 방문체크 배열(visited) 을 둬서 계산이 완료된 좌표의 경우 계산된 결과값을 리턴하는 방..

🥇코딩테스트:Algorithm

구현, 백트래킹 (15684 사다리 조작)

2024.02.16

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이과정 check() :i번 세로선의 결과가 i번이 나오는지 확인하는 함수 사다리 0개 놓고 check()하기 사다리 1개를 놓는 모든 경우에 대해 check()하기 사다리 2개를 놓는 모든 경우에 대해 check()하기 사다리 3개를 놓는 모든 경우에 대해 check()하기 만약 사다리 1개를 놓는 과정에서 check()==true가 된다면 사다리 2개, 3개 놓는 과정은 필요하지 않다. 왜..

🥇코딩테스트:Algorithm

백트래킹(14890 경사로)

2024.02.14

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 모든 행에 대해서 왼쪽에서 오른쪽으로 진행하며 지나갈 수 있는 길인지 확인하는 방식으로 문제를 풀었다. ✅왼쪽 블럭과의 높이 차이(gap) 계산 gap == 0 : 다음 칸으로 재귀 gap == 1 : 왼쪽 블럭에 계단을 놓을 수 있는지 확인한 후 다음 칸으로 재귀 gap == -1 : 이면 오른쪽 블럭에 계단을 놓을 수 있는지 확인한 후 계단 이후 칸으로 재귀 ✅백트래킹 종료(basecase) 조건 계단을 마지막 블럭..

🥇코딩테스트:Algorithm

BFS (백준 16234 인구이동)

2024.02.09

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이순서 0. 하루마다 NxN크기의 땅을 확인하며 국경을 허물었는지 확인 while(true){ if(!solve()){ // 국경 허물 수 있는지 확인하고 국경 허물고 인구수 갱신 break; } ans+=1; } 하루마다 (0,0)에서 bfs를 수행하며 국경을 허물고 인구를 이동시켰다. static boolean solve(){ visited = new boolean[N][N];..

🥇코딩테스트:Algorithm

두 지점이 동시에, 벽에 닿기 전 까지 움직이는 bfs (백준 13460 구슬탈출2)

2024.01.21

특이한 bfs문제 핵심 로직 1. 구슬을 동시에 움직이기 2. 벽에 닿기 직전까지 최대한 움직이기 3. 빨간 구슬과, 파란 구슬이 겹치는 경우를 처리 1. 구슬을 동시에 움직이기 빨간공과 파란공의 좌표를 같이 가지고 있는 Marble 클래스를 만들었다. class Marble{ private int redRow,redCol,blueRow,blueCol; public Marble(){} public Marble(int redRow, int redCol, int blueRow, int blueCol){ this.redRow = redRow; this.redCol = redCol; this.blueRow = blueRow; this.blueCol = blueCol; } public int getRedRow()..

🥇코딩테스트:Algorithm

벨만 포드 알고리즘

2024.01.12

간선 중심 알고리즘 👉 그래프들을 에지 리스트로 구현 음수 간선이 포함된 상황에서의 최단 거리 문제에 사용. 음수 간선의 순환을 감지할 수 있음. 매번 모든 간선을 전부 확인 최단 거리 리스트에서 업데이트 반복 횟수는 V - 1 시간복잡도 : O(VE), 다익스트 알고리즘에 비해 느리다 음수간선이 있어도 순환이 발생하지 않는다면 최단거리를 계산할 수 있다. (음수간선의 순환이 발생하면 최단거리가 음의 무한인 노드가 발생하게 됨) 동작원리 1. 출발 노드를 설정 2. 최단 거리 테이블을 초기화 3. 다음의 과정을 N-1 번 반복 3-1. 전체 간선 E개를 하나씩 확인 3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신 4. 만약 음수 간선 순환이 발생하는지 체크하고 싶다면 3..

티스토리툴바