프로그래머스. 동굣길
등교길이 아니라 등굣길이라니
1. 문제
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.
2. 제한사항
- 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
- m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다. - 물에 잠긴 지역은 0개 이상 10개 이하입니다.
- 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
3. 풀이
map[i][j]에서 목적지로 갈 수 있는 경로 수는map[i-1][j] + map[i][j-1]이다. 이걸 처음부터 끝까지 웅덩이 없는 곳만 골라서 반복하면 된다.집 -> 학교를 하니까 풀이가 생각이 안 나서 학교를 기준으로 보았다.- 학교의
위와왼쪽에서 올 수 있는 경우는 각각 한 가지씩이다. - 학교의 학교에서
위로 한 칸왼쪽으로 한 칸이동한 위치는오른쪽과아래쪽으로 갈 수 있어서 두 가지이다. - 여기까지 생각하고 학교에서 집으로 역추적 하기로 했다.
- 근데 loop를 반대로 돌리기 귀찮아서 지도를 뒤집기로 했다.
- 웅덩이도 맞춰서 뒤집어 주었다.
- 확실히 전 단계에서 확실히 처리된 값만 다루기 위해
row++를 먼저 해주고col++를 해주었다.
➕ 추가(20년 9월 30일)
- 생각해보니까 세로 먼저 안 하고 가로 먼저 해도 된다.
- 난 돌멩이다.
돌멩
4. 처음 코드와 달라진 점
- 코드 차이는 별로 없는데
- 지도를 열심히 뒤집다가 생각해보니까
집에서 학교를 가나학교에서 집을 가나 똑같다는 생각이 들었다.난 멍청이다. xy만 조금 수정해주었다.- 문제 구성 자체는 어렵지 않았는데
x와y가 계속 발목을 잡았다. - 그리고 2번 정도 수정해서 최종 제출 했는데
- 나머지 연산 안 해줌
- 웅덩이 연산 한군데 빼먹음
- 웅덩이 배열을 안 만들고도 할 수는 있을 것 같은데 bool 배열이고 있는게 훨씬 깔끔하게 나올 것 같아서 그냥 뒀다.
- 예외처리 많이 안하고 그냥 행과 열을 한 줄씩 추가해주면 코드가 더 깔끔해질 것 같았다.
수정했다. - 행과 열을 하나씩 추가했더니
map[1][1]을 1로 초기화해도 loop 돌면서 0으로 다시 초기화시키길래map[1][1]을 웅덩이로 처리해서 그냥 지나치게 해버렸다.
5. 코드(배열 크기 100X100)
#include <string>
#include <vector>
using namespace std;
int map[100][100];
bool puddle_map[100][100];
int solution(int m, int n, vector<vector<int>> puddles) {
map[0][0] = 1;
for(int i=0; i<puddles.size(); i++){
int x = puddles[i][1] - 1;
int y = puddles[i][0] - 1;
puddle_map[x][y] = true;
}
for(int i=1; i<n; i++){
if(puddle_map[i][0]) continue;
map[i][0] = map[i-1][0];
}
for(int i= 1; i<m; i++){
if(!puddle_map[0][i]) map[0][i] = map[0][i-1];
for(int j=1; j<n; j++){
if(puddle_map[j][i]) continue;
map[j][i] = (map[j-1][i] + map[j][i-1]) % 1000000007;
}
}
return map[n-1][m-1];
}5-2. 코드(101X101)
#include <string>
#include <vector>
using namespace std;
int map[101][101];
bool puddle_map[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
for(int i=0; i<puddles.size(); i++){
int x = puddles[i][1];
int y = puddles[i][0];
puddle_map[x][y] = true;
}
map[1][1] = 1;
puddle_map[1][1] =true;
for(int i= 1; i<=m; i++){
for(int j=1; j<=n; j++){
if(puddle_map[j][i]) continue;
map[j][i] = (map[j-1][i] + map[j][i-1]) % 1000000007;
}
}
return map[n][m];
}➕ 21.09.01 추가
6. 풀이
- 크게 달라진 건 없고
puddle_map배열을 만들지 않고 풀었다. puddle_map배열을 만들지 않아 연산이 아주 조금 복잡해졌다.arr를101 X 101배열로 만든다.i == 0 || j == 0인 배열의 항목은 0으로 초기화한다.i == 0 || j == 0인 배열의 항목은 실제 길이 아니라 계산을 위해만 존재한다,arr[1][1] = 1로 초기화 한다.puddles의 위치의arr는 0으로 초기화한다.- 0으로 초기화하면 다른 작업없이 더할 수 있다.
arr[i][j] = arr[i-1][j] + arr[i][j-1]이다.arr[1][1]이 다른 값으로 바뀌지 않기 위해i == 1 && j == 1이면 건너뛴다.puddle이 있는 위치는 계산을 하지 않고 건너 뛴다.
arr[n][m]을return하면 된다.
7. 코드
#include <string>
#include <vector>
using namespace std;
int solution(int m, int n, vector<vector<int>> puddles) {
int arr[101][101] = {0, };
for (int i = 1; i < 101; ++i) {
for (int j = 1; j < 101; ++j) {
arr[i][j] = -1;
}
}
for (vector<int> puddle : puddles) {
arr[puddle[1]][puddle[0]] = 0;
}
arr[1][1] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (arr[i][j] == 0 || (i == 1 && j == 1)) continue;
else arr[i][j] = (arr[i][j - 1] + arr[i-1][j]) % 1000000007;
}
}
return arr[n][m];
}