🔗 문제9376번: 탈옥 9376번: 탈옥상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타www.acmicpc.net 🖍 풀이백준 9376번 탈옥 이 글을 보고 문제를 풀었습니다.  백준 9376번 탈옥문제 링크입니다: https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모jaimemin.tistory.com  생각해내야 하는 점죄수 1이 죄수 2를 데리고 바깥으로 나가는 경우죄수 2가 죄수 1을 데리고 바..

🔗 문제 10711번: 모래성 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 🖍 풀이 문제의 조건 1 ≤ H, W ≤ 1,000 💡 파도가 몇번 칠지도 모르는데 이 범위를 2차원 배열을 이중포문으로 접근하는 건 TLE 가능성이 높다 그래서 모래가 있는 위치를 기준으로 BFS 했지만 시간 초과 🙂 시간 초과에 늪에 빠져서 🔗여기 에서 도움을 받았다. 처음엔 뭔 소리인지 모르겠어서 디버깅했더니 기존 코드의 실패 원인과 풀이 방법도 이해할 수 있었다. 📋 시간 초과 원인과 소스 코드 시..

🔗문제 1525번: 퍼즐 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 🖍풀이 한칸이 비워져있는 퍼즐을 순서대로 정렬하기 위한 최소 이동 비용을 구하는 문제 빈칸을 기준으로 사방의 셀을 옮겨가며 BFS방식으로 풀 수 있다. 🚩 2차원 배열이 아니라 문자열로 표현 빈칸을 기준으로 사방의 셀을 이동한다면 당연히 2차원 배열을 생각할 수 있지만, 이 풀이에서는 일련의 문자열로 취급해서 풀어주었다. 문자열에서 n 번째에 있는 빈칸을 x, y로 표현하는 법 문자열로 된 퍼즐을 BFS에 활용하는 법 최소 이동횟수를 구해야하기 때문에 이미 형성된 퍼즐을 큐에 넣으면 안된다. map이나 set를 활..

🔗 문제 17140번: 이차원 배열과 연산 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 크기가 3×3 (초기 배열 크기 3) 인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수

🔗 문제 20056번: 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. => 격자의 범위가 벗어나는 법은 없다. 5칸 짜리에서 8번칸 이동해야하면 3칸에 위치시키면 된다. ==> x%=N 🖍 풀이 간단하게 정리하면 이렇게 풀 수있다. while(K--) { // 1. 파이어볼의 동시 이동 // 2. 파이어볼 나누기 } 1...

🔗 문제 15683번: 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. CCTV의 최대 개수는 8개를 넘지 않는다. 🖍 풀이 문제를 보면 맵도 작고 CCTV 개수도 작기 떄문에 완전 탐색으로 풀어주었다. 소스를 보는게 빠를 듯하지만 설명을 해볼게요.. 현재..

🔗 문제 3190번: 뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 🖍 풀이 종료 조건을 보면 map의 범위를 벗어나거나 뱀 자기 자신과 부딪히면 게임이 종료된다. 뱀의 길이가 변하면서 이동하는 건 간단하게 deque로 해결했다. 머리를 내밀 때 push_front(), 꼬리가 짧아지면 pop_back()으로 해결했다. 더불어 map에 EMPTY, APPLE, SNAKE 세 종류의 데이터를 저장해서 뱀의 유무를 판단해주었다. 너무 친절하게도 시간 오름차순으로 방향 전환이 되어서 queue에 넣고 방향 전환시간이..

🔗 문제 20055번: 컨베이어 벨트 위의 로봇 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 🖍 풀이 문제를 정리해보자. 컨베이어 벨트가 오른쪽으로 움직인다. 당연히 로봇의 위치도 함께 움직인다. 이때 나가는 위치에 도달하면 로봇을 버린다. 적재한 로봇은 올라온 순서가 있다. 이 순서대로 로봇을 한 칸 더 이동시킨다. 이동하려는 곳의 내구성이 1 미만이면 이동하지 않는다. 이동하려는 곳에 로봇이 있으면 이동하지 않는다. 로봇을 이동한 후 이동하려는 곳의 내구성을 -1 더한다. 이때 나가..

🔗 문제 14500번: 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 🖍 풀이 모든 위치에서 탐색을 한다. 내 위치를 포함한 주변 위치를 총 4개를 모은다. 이게 테트로미노다. DFS로 4개를 만들든 BFS로 만들든 아무튼 인접한 공간 4개를 모으면 된다. 어떤 모양으로 모였나 디버깅하면 알겠지만 ㅗ, ㅜ, ㅏ, ㅓ 모양으로 방문하는게 어렵다는걸 알게 될 거다. BFS로 하면 만들 수 있는 줄 알았는데 안되길래 따로 oh()라는 함수로 방문해 줬다. (저주받은 작명) BFS로 풀면 508ms이고 D..

🔗 문제 16234번: 인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다..