반응형
시뮬레이션이란?
- 각 조건에 맞는 상황을 구현하는 문제(지도상에서 이동하면서 탐험?하는 문제, 배열 안에서 이동하면서 탐험? 하는 문제)
- 별도 알고리즘 없이 풀수 있으나, 구현력이 중요
- 매 시험마다 1문제 이상 무조건 출제
시간복잡도
- N * M
- 각 칸에서 4방향 연산 수행
자료구조
- 전체 지도 int[][]
- 내 위치, 방향; int, int, int
문제풀이
- 백준 14503
1.
// 입력 받기
string[] input = Console.ReadLine().Split();
int N = int.Parse(input[0]);
int M = int.Parse(input[1]);
input = Console.ReadLine().Split();
int y = int.Parse(input[0]);
int x = int.Parse(input[1]);
int d = int.Parse(input[2]);
int[][] map = new int[N][];
for (int i = 0; i < N; i++)
{
input = Console.ReadLine().Split();
map[i] = new int[M];
for (int j = 0; j < M; j++)
{
map[i][j] = int.Parse(input[j]);
}
}
int cnt = 0;
int[] dy = { -1, 0, 1, 0 }; // 북, 동, 남, 서
int[] dx = { 0, 1, 0, -1 };
- 입력값 에 대한 선언과 북동남서 값 선언
2.
while (true)
{
// 현재 칸이 청소되지 않은 경우 청소
if (map[y][x] == 0)
{
map[y][x] = 2; // 청소 완료 표시
cnt++;
}
}
- while문을 선언하고 청소되지 않은 칸이면 청소 처리
3.
bool sw = false;
// 4방향 탐색
for (int i = 1; i <= 4; i++)
{
// 반시계 방향으로 회전 (d-i+4)%4
int nd = (d - i + 4) % 4;
int ny = y + dy[nd];
int nx = x + dx[nd];
if (0 <= ny && ny < N && 0 <= nx && nx < M)
{
if (map[ny][nx] == 0)
{
d = nd;
y = ny;
x = nx;
sw = true;
break;
}
}
}
- 4방향으로 탐색을 할때 반시계 방향으로 하라고 했으니 "(d - i + 4) % 4;"로 해서 반 시계 방향으로 돌며 빈 공간 찾기
4.
// 4방향 모두 갈 수 없는 경우
if (!sw)
{
// 후진 방향 계산
int ny = y - dy[d];
int nx = x - dx[d];
if (0 <= ny && ny < N && 0 <= nx && nx < M)
{
if (map[ny][nx] == 1) // 벽이면 종료
{
break;
}
else // 벽이 아니면 후진
{
y = ny;
x = nx;
}
}
else // 범위를 벗어나면 종료
{
break;
}
}
- 만약 4방향 모두 청소할 곳이 없다면 현재 방향을 유지한 상태에서 반대 방향으로 이동
- 범위를 벗어나거나 벽이면 종료
최종코드
public class num_14503
{
static void Main(string[] args)
{
// 입력 받기
string[] input = Console.ReadLine().Split();
int N = int.Parse(input[0]);
int M = int.Parse(input[1]);
input = Console.ReadLine().Split();
int y = int.Parse(input[0]);
int x = int.Parse(input[1]);
int d = int.Parse(input[2]);
int[][] map = new int[N][];
for (int i = 0; i < N; i++)
{
input = Console.ReadLine().Split();
map[i] = new int[M];
for (int j = 0; j < M; j++)
{
map[i][j] = int.Parse(input[j]);
}
}
int cnt = 0;
int[] dy = { -1, 0, 1, 0 }; // 북, 동, 남, 서
int[] dx = { 0, 1, 0, -1 };
while (true)
{
// 현재 칸이 청소되지 않은 경우 청소
if (map[y][x] == 0)
{
map[y][x] = 2; // 청소 완료 표시
cnt++;
}
bool sw = false;
// 4방향 탐색
for (int i = 1; i <= 4; i++)
{
// 반시계 방향으로 회전 (d-i+4)%4
int nd = (d - i + 4) % 4;
int ny = y + dy[nd];
int nx = x + dx[nd];
if (0 <= ny && ny < N && 0 <= nx && nx < M)
{
if (map[ny][nx] == 0)
{
d = nd;
y = ny;
x = nx;
sw = true;
break;
}
}
}
// 4방향 모두 갈 수 없는 경우
if (!sw)
{
// 후진 방향 계산
int ny = y - dy[d];
int nx = x - dx[d];
if (0 <= ny && ny < N && 0 <= nx && nx < M)
{
if (map[ny][nx] == 1) // 벽이면 종료
{
break;
}
else // 벽이 아니면 후진
{
y = ny;
x = nx;
}
}
else // 범위를 벗어나면 종료
{
break;
}
}
}
Console.WriteLine(cnt);
}
}
참고영상
- 바로가기
반응형
'기타 > 코딩테스트 공부' 카테고리의 다른 글
[필수 알고리즘] 이진탐색 (0) | 2025.05.03 |
---|---|
[필수 알고리즘] 투포인터 (0) | 2025.05.03 |
[필수 알고리즘] 백 트래킹 (0) | 2025.05.03 |
[필수 알고리즘] DFS (0) | 2025.05.03 |
[필수 알고리즘] BFS (0) | 2025.05.03 |