TIL (2022.03.12)
➕ 오늘 푼 문제
➕ 아이디어
문제를 이해하기 어려워 지문부터 정리해보자면 다음과 같다.
- 경로 사이클이란?
- 시작점에서 출발한/나간 방향과 동일한 방향으로 시작점에 도착하는/들어오는 경우, 경로 사이클이 형성된다.
- 시작점이 아닌 경우, 같은 지점을 같은 방향으로 들어왔다면 경로 사이클은 형성될 수 없다.
- 같은 지점을 같은 방향으로 들어왔다면, 이후 진행 패턴이 이전과 동일하기 때문에 사이클이 형성될 수 없다.
- 출발 방향은 4가지 방향을 모두 고려한다. (위, 아래, 오른쪽, 왼쪽)
- 시작점은
grid내의 모든 점이 가능하다. 즉, 모든 점을 시작점으로 고려해야 한다.
- 경로 사이클의 길이를 오름차순으로 정렬하여 반환한다.
위의 내용을 구현하기 위한 아이디어는 다음과 같다.
- 경로 사이클 판별
- 지점의 위치와 나가는 방향을 표현하는 3차원 배열(
visited)를 선언한다. - 모든 지점/방향을 시작점/시작 방향으로 고려하여, 이동하는 것을 시뮬레이션 한다.
- 무한 반복문을 돌며,
- 만약 이미 해당 방향으로 방문한 적이 있다면, 사이클이 형성될 수 없으므로 반복문을 종료한다. (→ 이게
visited를 매 반복마다 초기화하면 안되는 이유다! 아래서 좀 더 자세히 설명해보겠다.) - 방문한 적이 없다면, 방문 처리를 한 후 다음 위치로 이동한다. 이때 사이클의 길이는 1만큼 증가한다.
- 만약 이동한 위치가 시작점과 같고 이동 방향도 시작 방향과 같다면, 사이클이 형성된 것이므로
answer에 사이클의 길이를 추가하며 종료한다.
- 만약 이미 해당 방향으로 방문한 적이 있다면, 사이클이 형성될 수 없으므로 반복문을 종료한다. (→ 이게
- 무한 반복문을 돌며,
- 지점의 위치와 나가는 방향을 표현하는 3차원 배열(
- 방향 전환
-
현재 방향을 기준으로 오른쪽, 혹은 왼쪽으로 움직이는 경우 다음과 같이 작성하면 쉽게 구현할 수 있다
# D, L, U, R 순으로 나열 (마름모 형태로 순환되어야 한다!) dx = [1, 0, -1, 0] dy = [0, -1, 0, 1] # 왼쪽으로 이동 d = (d-1)%4 # 오른쪽으로 이동 d = (d+1)%4
-
- 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 이동
- 격자를 넘어가지 않게, 격자의 길이만큼 나눈 나머지를 새로운 좌표로 한다. 이때 음수 값이 나오지 않기 위해 격자의 길이만큼 더해 준 후 나머지 연산을 한다.
- 참고로 파이썬은 음수 나머지 연산을 할 때 자동으로 위와 같은 로직으로 처리된다. 따라서 격자의 길이를 더할 필요 없이 나머지 연산을 해도 된다.
[참고] visited 를 매 반복마다 초기화하면 안되는 이유
처음에 코드를 짤 때는 매 시작 지점/방향마다 사이클이 있는지 확인해야 한다고 생각해, 아래 코드처럼 매번 visited를 초기화 해야 한다고 생각했다.
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
for(int k=0; k<4; k++){
visited = new int[n][m][4]; // 매 반복마다 vistied 초기화
int x = i, y = j, d = k;
int count = 0;
// 이하 생략하지만, 이 경우 주어진 테스트 케이스에서 모든 경우에 다 사이클이 생성되는 것으로 판별했다!
즉, ["SL", "LR"] → [16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16] 식으로 결과가 나오는 것이다.
예시로 주어진 그림을 보며 그 이유를 확인할 수 있었다.
visited 가 매 반복마다 초기화 되면, 한 사이클에 속하는 경로로 시작하는 모든 경우를 새로운 사이클로 판별한다. 즉, 1번 경로에서 시작하나 5번 경로에서 시작 하나 모두 다른 사이클로 판별한다는 뜻이다. 하지만 우리가 원하는 것은 이 경우를 모두 같은 사이클로 취급하는 것이다.
그래서 한 번 방문한 경로는 다시 방문하지 않도록 visited 를 계속 갱신하여 문제를 해결할 수 있었다.
➕ Java 코드
import java.util.*;
class Solution {
public int[] solution(String[] grid) {
int[] answer = {};
List<Integer> result = new ArrayList<Integer>();
int n = grid.length, m = grid[0].length();
int[][][] visited = new int[n][m][4];
int[] dx = {0, -1, 0, 1};
int[] dy = {-1, 0, 1, 0};
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
for(int k=0; k<4; k++){
int x = i, y = j, d = k;
int count = 0;
while(visited[x][y][d] == 0){
visited[x][y][d] = count++;
// 방향 전환
char now = grid[x].charAt(y);
if(now == 'R'){
d = (d + 1 + 4) % 4;
}else if(now == 'L'){
d = (d - 1 + 4) % 4;
}
// 좌표 이동
x = (x + dx[d] + n) % n;
y = (y + dy[d] + m) % m;
if(x == i && y == j && k == d){
result.add(count++);
break;
}
}
}
}
}
answer = new int[result.size()];
for(int i=0; i<result.size(); i++){
answer[i] = result.get(i);
}
Arrays.sort(answer); // 오름차순으로 값 정렬
return answer;
}
}➕ Python 코드
def solution(grid):
answer = []
visited = [[[0 for k in range(4)] for j in range(len(grid[0]))] for i in range(len(grid))]
dx = [1,0,-1,0] # D, L, U, R 순
dy = [0,-1,0,1]
for x in range(len(grid)):
for y in range(len(grid[0])):
for d in range(4):
nx, ny, nd = x, y, d
count = 0
while True:
if visited[nx][ny][nd] != 0:
break
count += 1
visited[nx][ny][nd] = count
nx = (nx + dx[nd]) % len(grid)
ny = (ny + dy[nd]) % len(grid[0])
if grid[nx][ny] == 'R':
nd = (nd+1)%4
elif grid[nx][ny] == 'L':
nd = (nd-1)%4
if (nx, ny, nd) == (x, y, d):
answer.append(count)
break
return sorted(answer)➕ 궁금한 내용 및 소감
- 문제가 잘 이해되지 않아서, 결국은 다른 풀이 방법을 찾아보면서 풀었다. 문제 자체에 설명이 조금 부족했던 것 같다. 이번 문제에서 개인적으로 핵심이라고 생각하는 부분은 다음과 같다.
- 3차원 배열로 방문 여부 확인
- 경로 사이클인지 아닌지를 판별하기 위해서는 방문 여부를 꼭 확인해야 했다. 이때 고려되는 사항은 방문한 지점의 위치와 (나간)방향이므로 , 이를 3차원 배열로 표현할 수 있다.
- 방향 전환
- 오른쪽인 상태에서 오른쪽 이동 혹은 왼쪽인 상태에서 왼쪽으로 이동하는 등의 복잡한 방향 전환이 필요했다. 보통 이런 문제가 나오면 직접 경우의 수를 모두 만들어서 저장해두고 사용했었는데, 이렇게 하면 틀릴 가능성도 높고 시간이 매우 오래걸린다.
- 아이디어 파트에도 정리해 두었는데, 방향 전환은 수식으로 간단하게 표현할 수 있다. 마름모 형태로 순환하듯이 방향을 배치하면 +1, -1 연산으로 이동할 수 있으니 꼭 기억해두자!
- 3차원 배열로 방문 여부 확인
➕ 참고 문헌
- 아이디어
- 참고 링크: [프로그래머스] 빛의 경로 사이클 파이썬
- Python - %(modulo) 연산
.
make it mine, make it yours