개발조아

문제 링크 : https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 바로 전에 풀이한 배열에서 이동과 아주 유사하다. https://westmino.tistory.com/69 [BOJ/백준] 1981 배열에서 이동 파이썬 문제 링크 : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 ..

문제 링크 : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 접근법을 모르겠어서 알고리즘을 찾아보고 푼 문제이다. 핵심은 투포인터를 이용하는 것이다. 배열의 숫자 리스트를 정렬해서 따로 만들고 투포인터로 최소, 최대값을 결정하고 BFS 실행 후 조정해간다. BFS를 실행할때 시작점과 그리고 중간에 들르는 점들에 대해서 이전에 정한 최소, 최대값 범위에 포함되는지 체크해야한다. 모든 점이 범위를 통과하고 목표점에 도달했다..

문제 링크 : https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 비트마스킹으로 해결한 문제이다. 예전에 풀었던건데 그때는 BFS+DFS로 풀었다. 이 방법은 느리다. 모든 시작점과 더러운칸에서 BFS를 진행하고 마지막에 DFS를 진행 했기 때문이다. 그때의 알고리즘은 아래 더보기를 누르면 된다. 더보기 시작점과 더러운칸에 0부터 번호를 매기고 start라는 배열에 번호를 저장했다. 그리고 start배열의 점에서 각각 BFS를 실행하여 각 점사이의 거리 최..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 막상 풀고보니 그렇게 어려운 문제가 아닌듯 했다. 물론 생각하는데 좀 걸렸지만, 그래도 두시간정도 걸린듯 하다. 로봇을 상하좌우, 회전하여 n,n칸으로 이동할 때 최소 시간을 구하는 문제이다. 로봇의 좌표가 두개이고 n의 크기가 100으로 작아서 4차원 배열로 방문 체크를 했다. 최소 시간을 구하라해서 BFS를 이용했다. 로봇의 이동은 그냥 두좌표 동시에 상하좌우 이동시키고 유..

문제 링크 : https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net BFS + 구현 문제이다. 알고리즘 자체는 어렵지 않으나 상태값을 잘못 지정하여 틀리고 있었다. 문제는 간단하다. 맵에 특정칸에는 다른 칸의 조명을 켤수 있는 스위치가 있고, 주인공은 상하좌우로 조명이 켜진 칸으로만 이동이 가능하다. 한 스위치로 여러개의 조명을 컨트롤 가능하고 한 조명이 여러 스위치에 의해 컨트롤이 가능하다. 이..

문제 링크 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net BFS, 백트레킹, 조합 다 써볼수 있는 좋은 문제라고 생각한다. 문제는 비교적 간단하다. 요약하면 아래와 같다. 배양액의 종류는 두개이고 이 배양액을 놓을 수 있는 칸은 최대 10개 이하로 정해져있다. 배양액을 넣을 수 있는 칸에 주어진 배양액 전부 적절히 분배하고 확산시킨다. 이때 배양액은 동서남북 방향으로 퍼지며 물로는..

문제 링크 : https://www.acmicpc.net/problem/2917 2917번: 늑대 사냥꾼 첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다. www.acmicpc.net 문제를 잘 이해를 못해서 좀 고민했다. 가장 안전한 길이란 모든 칸에서 나무와 거리의 최솟값이 가장 큰 경로이다. 이 부분에서 최솟값이 가장 큰 경로라길래 최솟값이 가장 크면 가장 작은 값인가 큰값인가 헷갈렸었다. 아주 멍청이 같은 생각이었다. 모든 점에서 나무까지의 거리 중 최소값을 찾아서 저장하고 이동 중에 이 거리가 큰값을 선택해서 가면 된다. 모든 점에서 나무까지의 거리는 BFS로 돌..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 질문하기에 너무 공감됐던 글이다. 1,2주차는 쉬웟는데 갑자기 너무 어려워졌던 문제였다. 올해 LG CNS 8월 입사자 4번 문..