https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net # 3차원 visited배열을 이용한 bfs문제이다. # visited배열을 3차원으로 선언해 벽을 부셨을때는 visited[1][x][y], 안 부셨을 때는 visited[0][x][y] 이런식으로 저장해주었다. # bfs함수: 현재 좌표가 도착지점이라면 visited[b][x][y]를 return해준다. 일반 bfs함수처럼 상하좌우를 탐색하는데, m[nx][ny]가 0..
https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net # 카톡방에 누가 질문을 올려서 재밌어보이길래 풀어봤다. 마침 이번주에 BFS문제를 연속으로 풀고 있어서 쉽게 풀었다. # A를 B로 바꾸는 과정에서도 4자리수가 유지되어야 하고 소수이어야 하므로 get_primes함수를 통해 1000과 10000사이의 소수를 모두 구해준다. (1060개정도밖에 되지 않는다.) get_primes함수에서 소수를 구하는 과정은 '에라토스테네스의 체' 방법을 사용하였다. # ..
https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net # 문제자체는 어렵지 않지만 엄청난 삽질을 한 문제이다. # 처음에 문제를 제대로 읽지 않아 '그람'이 벽을 한번만 부술 수 있는 줄 알았다. 그래서 '벽 부수고 이동하기' 문제처럼 visited배열을 3차원으로 만들어서 벽을 부셨을 때와 벽을 부수지 않았을 때 2가지 상태를 저장했다. 물론, 이렇게도 푼 사람들도 많다. # 하지만, 문제를 잘 읽어보니 '그람'이 부술수 있는 벽의..
https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net # BFS+시뮬레이션 문제이다. # 최근에 푼 문제중에 가장 오래걸렸다.. * bfs함수: (15 ~ 20라인)은 현재 좌표기준으로 상하좌우를 탐색하면서 m[nx][ny]가 2인지 아닌지 판단한다. m[nx][ny]가 2이면 공기와 닿아있는 좌표이므로 move에 넣어주고 cnt를 1증가시킨다. 상하좌우 중 한 곳이라도 공기와 닿아있으면 녹으므로 바로 break를 해준다. 맵 탐색을 마친뒤 [cnt, mov..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net # 2018 하반기 삼성SW역량테스트 문제이다. # 삼성기출에서 자주 나오는 시뮬레이션 문제이다 (BFS를 곁들인..) # '인구 이동'하는 것이 최근 삼성기출에 나온 '미세먼지 안녕!'에서 미세먼지가 확산하는 것과 비슷하다고 느껴져서 빠르게 접근해서 푼 것 같다. * bfs함수: q에서 pop을 해준 좌표를 기준으로 상하좌우를 탐색하며 (nx, ny)가 좌표 밖을 벗어나지 않고 방..
https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr # 저번주부터 매주마다 한 문제씩 공개되는 weekly challenge이다. 이번 주 문제는 저번 주보다는 어려웠지만, 단순 구현문제였다. 1. 학생들이 받은 점수는 가로 값을 보는 것이 아니라 세로값을 봐야 하므로 2중 for문에서 scores[j][i]로 s에 append해주었다. 2. 자기 자신..
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net # '숨바꼭질' 문제와 다르게 순간이동을 할때는 시간이 0초가 걸린다. 가중치가 다른 문제에서는 단순 BFS를 돌리면 안된다. 따라서, 가중치에 우선순위를 사용한 BFS를 사용하거나 다익스트라 알고리즘을 사용하면 된다. (나는 다익스트라를 사용했다.) # 처음에 N위치에서 출발하므로 start에 N을 넣고 dijkstra를 돌린다. - dijkstra함수: q의 ..
https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net # 시간제한이 12초인 문제는 처음본다.. I. 처음에 A, B배열의 모든 원소의 합을 AB배열에 넣고, C, D배열의 모든 원소의 합을 CD배열에 넣은 뒤 정렬 한뒤 투 포인터를 사용해 합이 0인 경우를 count해주려고 했지만, AB = [0, 0, 0, 0], CD = [0, 0, 0, 0]인 경우 합이 0인 경우 두 포인터 중 하나가 무조건 이동하므로 또 0이 나오는 경우..
모르는 사이에 조금씩 조금씩..
