Jupyter Notebook 원격 접속 세팅하기(윈도우10)

|

Jupyter Notebook 원격 접속 세팅하기(윈도우10)

  • 윈도우 10 에서 Jupyter Notebook 원격 접속을 세팅한다.
  • 일부 환경(직장이나 연구실 등)에서는 Port가 막혀있을 수 있으므로 별도 포트 세팅이 필요하다.

노트북 세팅하기

  • Anaconda prompt 실행 후 아래 입력
    • jupyter notebook --generate-config
    • 노트북 세팅용 jupyter_notebook_config.py이 이어지는 디렉터리에 생성된다.
      • 일반적으로 C:\Users\user_name\.jupyter에 생성됨
  • 암호 설정하기
    • Anaconda prompt에서 ipython 입력
    • ipython에서 from notebook.auth import passwd 입력
    • passwd() 입력 후 노트북용 비밀번호 설정
      • Verify 번호까지 정확하게 입력해야 함
    • 세팅 완료 후 quit()으로 ipython 빠져나오기
    • 여기서 출력되는 ssh값을 복사해둔다.
  • 에디터로 jupyter_notebook_config.py 열기
    • 파일 내에서 아래와 같이 해당 주석을 찾아서 삭제 후 수정
      • 포트 번호의 경우 맘에드는 복잡한 5자리 임의의 숫자로 설정한다.

...

#c.NotebookApp.ip = 'localhost'
c.NotebookApp.ip = '*'

#c.NotebookApp.password = ''
c.NotebookApp.password = 'sha1:SHA_VALUES'

#c.NotebookApp.password_required = False
c.NotebookApp.password_required = True

#c.NotebookApp.port = 8888
c.NotebookApp.port = YOUR_PORT_NUMBER


방화벽에서 포트 열기

  • 윈도우 키 누른 후 방화벽 검색해 “방화벽 상태 확인” 클릭 후 열기
  • 방화벽에서 왼쪽 고급 설정 클릭
  • 고급 설정에서 인바운드 규칙 클릭
  • 인바운드 규칙에서 우측 새 규칙 클릭
    • 포트 선택 후 다음 클릭
    • TCP 선택 후 특정 로컬 포트 에 위에서 설정한 포트 번호 5자리(YOUR_PORT_NUMBER) 입력 후 다음 클릭
    • 연결 허용 선택 후 다음 클릭
    • 도메인, 개인, 공용 모두 선택 후 다음 클릭
    • 이름 에 “Remote jupyter connection” 과 같이 알아 볼 수 있게 설정 후 마침 클릭
  • 컴퓨터 재시작, 또는 서비스-Remote Desktop Services 재시작 후 사용!

사용하기

  • Anaconda prompt 실행 후
    • jupyter notebook --ip=YOUR_IP 입력 후 실행
  • 원격 디바이스에서 웹 브라우저를 킨 후
    • YOUR_IP:YOUR_PORT_NUMBER 입력 후 접근
    • 이 때, 비밀번호를 입력하라고 뜨는데 여기서 비밀번호는 위 ipython에서 설정한 비밀번호를 입력하면 됨

191009 백준 알고리즘 문제풀기

|

[16236] 아기 상어

  • 난이도: 상
  • 문제 풀이 떠올리는데 30분, 구현까지 해서 2시간 넘게 걸림.
  • 너무 조건이 많아 어렵다
  • 어이없는것은 분명 반례까지 다 맞았는데 자꾸 틀렸다고 채점된다. 이유를 모르겠다.

  • 문제
    • https://www.acmicpc.net/problem/16236
    • NxN 크기 맵이 주어지고, 아기 상어와 물고기들이 주어진다.
      • 물고기와 상어는 각 1칸씩 차지한다.
    • 처음 아기 상어 크기는 2이고, 1초마다 상하좌우 1칸씩 움직일 수 있다.
      • 자신과 크기가 같거나 작은 고기는 지나갈 수 있고, 크기가 작은 물고기만 먹을 수 있다.
      • 자신 크기의 개수만큼 물고기를 먹으면 크기가 1 증가한다.
    • 아기 상어 이동 결정은 다음과 같다.
      • 더 이상 먹을 수 있는 물고기가 공간에 없으면 엄마 상어에게 도움을 요청한다.
      • 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
      • 먹을 수 있는 물고기가 1마리보다 많으면 거리가 가장 가까운 고기를 먹는다.
        • 아기상어는 항상 가까운 길로만 다닌다.
        • 가까운 물고기가 많다면 가장 위에 있는 물고기, 그중에서도 가장 왼쪽에 있는 물고기를 먹는다.
    • 이동은 어느칸이건 무조건 1초가 걸리고, 물고기를 먹는데 걸리는 시간은 없다.
      • 물고기는 이동과 동시에 먹는다.
    • 공간 상태가 주어졌을 때 아기 상어가 몇 초 동안 엄마 상어에게 도움 요청없이 물고기 먹을 수 있는지를 계산한다.
  • 풀이
    • 문제를 나누면
      • 물고기 상태 맵을 입력 받는다.
        • 입력 시엔 상어 위치만 저장하고 해당 위치를 0으로 초기화해서 지나갈 수 있는 상태로 만든다.
      • 상어가 갈 수 있는데를 찾고
      • 물고기를 먹고
      • 먹은 상태에 따라 상어 크기를 키운다.
        • 만약 먹을 수 있는 고기가 없었다면 끝낸다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

struct shark {
	int x, y, size;
};

int map[22][22];
int check[22][22];

int dx[] = { 0,-1,1,0 };
int dy[] = { -1,0,0,1 };

void init_check(int n)
{
	for (int j = 0; j < n; j++)
	{
		for (int i = 0; i < n; i++)
		{
			check[j][i] = 0;
		}
	}
}

void shark_grow(int &eat_cnt, shark &baby)
{
	if (eat_cnt == baby.size)
	{//만약 먹은량이 상어크기와 같다면
		baby.size++; // 상어 크기 키우고
		eat_cnt = 0; // 먹은량 초기화
	}
}

int main()
{
	int N;
	scanf("%d ", &N);
	shark baby;
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] == 9)
			{
				baby.x = i;
				baby.y = j;
				baby.size = 2;
				map[j][i] = 0;
			}
		}
	}

	int answer = 0;
	bool flag = false;
	int eat_count = 0;
	int timer = 0;
	while (1)
	{
		//더 이상 먹을 고기 없는 경우 빠져나간다.
		if (flag) break;

		//check 맵 매 초마다 초기화
		init_check(N);

		//상어 현재 위치 check
		queue<pair<int, int>> q;

		int cx = baby.x;
		int cy = baby.y;
		
		check[cy][cx] = 1;
		q.push(make_pair(cx, cy));
		bool eat = false;
		
		int distance = 1000;
		int min_x = 1000;
		int min_y = 1000;

		while (!q.empty())
		{
			cx = q.front().first;
			cy = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++)
			{ //상어 다음 위치를 간다.
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (0 <= nx && nx < N && 0 <= ny && ny < N&&check[ny][nx] == 0 && map[ny][nx] <= baby.size)
				{//맵 영역 안이고, 간 적이 없고, 맵 물고기 크기가 상어 이하라면 간다.
					//일단 방문한다.
					check[ny][nx] = check[cy][cx] + 1;
					q.push(make_pair(nx, ny));
					if (0 < map[ny][nx] && map[ny][nx] < baby.size)
					{//먹을 수 있는 물고기가 존재한다면
						eat = true; // 먹는다고 표시 하고
						if (check[ny][nx] < distance)
						{//만약 지금 방문한 위치가 가장 가깝다면
							min_x = nx; // 최소 위치 초기화
							min_y = ny;
							distance = check[ny][nx];
						}
						else if (check[ny][nx] == distance)
						{//만약 지금 방문한 거리가 가장 가까운 거리와 같다면
							int temp = min_x;
							if (ny < min_y)
							{ // 가장 위의 물고기를 먹고
								min_x = nx;
								min_y = ny;
								if (nx < temp)
								{ // 그중에서도 왼쪽 물고길 먹는다.
									min_x = nx;
									min_y = ny;
								}
							}
						}
					}					
				}
			}
		}
		if (eat)
		{//먹은 고기가 있다면
			eat_count++; // 먹는다.
			baby.x = min_x; // 상어 위치 초기화
			baby.y = min_y;
			map[min_y][min_x] = 0; //먹힌 물고기 지우기
			timer += check[min_y][min_x] - 1; // 먹는데 걸린 시간 더하기

			//상어를 조건에 맞게 키운다.
			shark_grow(eat_count, baby);
		}
		else flag = true; //맵에 먹을 고기 없으면 끝낸다.
	}
	printf("%d\n", timer);
  
	//std::system("pause");
	return 0;
}

191009 백준 알고리즘 문제풀기

|

[14499] 주사위 굴리기

  • 난이도: 하
    • 시뮬레이션 문제로, 푸는데 총 1시간 반 소요됨.
      • 문제 이해하는데 40분, 구현하는데 30분 미만, 디버깅에 30분 걸린 듯 하다.
    • 어려운 문제는 아니였지만, 시뮬레이션의 조건을 잘못 파악하고 실수를 해서 40분이상을 날려먹었다.
      • 조건을 하나 잘못 이해해서 시간을 많이 날려먹었다.
      • 조건을 정확하게 파악하고 정리해두는것이 제일 중요한듯하다.
    • 제일 관건이 되는것은 주사위를 굴리는것 정도로 매우 쉬운 난이도였다.
      • 각각 주사위를 오른쪽, 왼쪽, 위, 아래로 굴릴 때의 case를 분류하고, 이에 맞게 동작하게 하면 됐다.
    • 또한, 행/렬 실수로 시간을 또 날려먹었다.
      • 제일 자주하고 반복되는 실수로.. 꼭 정확하게 파악하고 문제를 풀기 시작해야 한다.
    • 이전에는 시뮬레이션 문제를 맞닥뜨리면 무조건 풀기 시작했다.
      • 이럴 경우 결국 풀지 못하게 되는 경우도 많고 코드도 뒤죽박죽 되버린다….
    • 어떤 문제건, 문제의 조건과 상황을 완벽하게 이해하고 풀기 시작해야 안정적으로 푸는것이 가능하다.
    • 시뮬레이션 문제는 반드시
      • 문제를 정확하게 이해하고
      • 모든 조건을 정확하게 파악하고
      • case를 정확하게 분리해서 푸는것이 중요함
  • 문제
    • https://www.acmicpc.net/problem/14499
    • 크기가 NxM 맵에서 주사위 좌표가 순서대로 y,x 좌표로 주어질 때, 전체 맵에 바닥에 쓰이는 수 또한 입력된다.
    • k번의 이동횟수와 이에 대한 주사위 회전 방향이 입력된다.
    • k 번동안 주사위 맨 위의 숫자를 출력한다.
    • 조건
      • 주사위는 주어진 맵 안에서만 굴릴 수 있다.
      • 주사위가 처음 놓이는 위치의 숫자는 무조건 0이다.
      • 지도의 각 칸에는 정수가 하나씩 쓰여있다.
      • 주사위는 동(1), 서(2), 북(3), 남(4) 방향으로 움직인다.
      • 주사위를 굴렸을 때
        • 이동한 칸에 쓰여 있는 수가 0이면 주사위 바닥면의 숫자가 칸으로 복사된다.
          • 단, 주사위 숫자는 0이되는것이 아니라 유지된다!
          • 이것을 오해해서 시간을 꽤 날려먹음..
        • 이동한 칸에 숫자가 쓰여 있다면, 주사위 바닥면의 숫자가 칸의 숫자로 초기화되고 칸은 0이 된다.
  • 풀이
    • 문제를 나눠보면
      • 입력을 받아 맵과 명령어들을 저장한다.
      • 전체 명령어동안
      • 주사위를 굴린다.
        • 주사위는 맵 안으로만 구를 수 있다.
        • 맵 밖으로 넘어가면 그냥 넘어간다.
      • 주사위가 굴러간 위치의 맵의 값에 따라 주사위와 값을 초기화한다.
        • 맵에 값이 있다면 주사위 값을 초기화하고 맵을 비우고
        • 맵에 값이 없다면 맵 값만 초기화한다.
      • 현재 위치를 굴러간 위치로 초기화한다.
    • 주사위는 십자가 모양으로 나열한 후, 순서대로 0부터 5까지 매핑한다.
      • 이렇게 되면 주사위의 위쪽은 항상 인덱스 2가 된다.
        • 값을 출력할땐 주사위의 2번 인덱스 값만 출력하면 됨
      • 아래쪽은 항상 인덱스 5가 된다.
        • 값을 초기화 할 댄 5번 인덱스 값만 초기화 하면 됨
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int map[21][21]; // 주사위 맵
vector<int> order; // 명령어 저장용

int dx[] = { 0,1,-1,0,0 }; // 주사위 굴리기 방향
int dy[] = { 0,0,0,-1,1 };

int dice[] = { 0,0,0,0,0,0 }; // 주사위 값

void rotate_dice(int dir)
{
	int t_dice[] = { 0,0,0,0,0,0 };
	if (dir == 1)
	{//오른쪽 회전
		t_dice[0] = dice[0];
		t_dice[1] = dice[5];
		t_dice[2] = dice[1];
		t_dice[3] = dice[2];
		t_dice[4] = dice[4];
		t_dice[5] = dice[3];
	}
	if (dir == 2)
	{//왼쪽 회전
		t_dice[0] = dice[0];
		t_dice[1] = dice[2];
		t_dice[2] = dice[3];
		t_dice[3] = dice[5];
		t_dice[4] = dice[4];
		t_dice[5] = dice[1];
	}
	if (dir == 3)
	{//위 회전
		t_dice[0] = dice[2];
		t_dice[1] = dice[1];
		t_dice[2] = dice[4];
		t_dice[3] = dice[3];
		t_dice[4] = dice[5];
		t_dice[5] = dice[0];
	}
	if (dir == 4)
	{//아래 회전
		t_dice[0] = dice[5];
		t_dice[1] = dice[1];
		t_dice[2] = dice[0];
		t_dice[3] = dice[3];
		t_dice[4] = dice[2];
		t_dice[5] = dice[4];
	}
	for (int i = 0; i < 6; i++)
	{ // 계산된 주사위를 원래 주사위로 초기화
		dice[i] = t_dice[i];
	}
}

int main()
{
	int H, W, x, y, k;
	scanf("%d %d %d %d %d", &H, &W, &y, &x, &k);
	
	for (int j = 0; j < H; j++)
	{
		for (int i = 0; i < W; i++)
		{
			scanf("%d", &map[j][i]);
		}
	}

	for (int i = 0; i < k; i++)
	{
		int t;
		scanf("%d", &t);
		order.push_back(t);
	}

	int cx = x; // 현재 위치를 받고
	int cy = y;
	for (int i = 0; i < k; i++)
	{//전체 명령어 동안
		int nx = cx + dx[order[i]]; // 다음 위치를 만든다음
		int ny = cy + dy[order[i]];

		//만약 범위 벗어나지 않는다면
		if (0 <= nx && nx < W && 0 <= ny && ny < H)
		{
			//주사위 회전시키고
			rotate_dice(order[i]);

			//주사위 값 초기화와 맵 값 채우기
			if (map[ny][nx] != 0)
			{//만약 map에 값이 있다면
				dice[5] = map[ny][nx]; // 주사위 값 초기화
				map[ny][nx] = 0; // 맵을 비운다.
			}
			else
			{//만약 map에 값이 없다면(0)
				map[ny][nx] = dice[5]; // 맵 값을 초기화
			}
			printf("%d\n", dice[2]); // 주사위 위쪽 출력
			cx = nx; // 다음 위치 초기화
			cy = ny;
		}
	}
	//std::system("pause");
	return 0;
}

191008 백준 알고리즘 문제풀기

|

[17143] 낚시왕

  • 난이도: 상
    • 시뮬레이션 문제로, 푸는데 총 2시간 소요됨..
      • 문제 풀이를 떠올리는데는 30분 미만이 소요되었지만 구현에 90분 이상 소요되었다.
      • 전체 틀을 짜는거는 30분도 안걸렸지만, 상어가 다음 위치로 움직이는 것을 처리하는데에서 엄청난 시간이 소요되었다.
    • 낚시왕 큰 문제를 작게 쪼개고, 순서대로 차근차근 접근해보니 이전보다 합리적인 방법으로 해결을 해메이지 않고 풀 수 있었다.
      • 입력을 받아 물고기 맵(구조체 활용)을 만들고
      • 낚시왕을 한칸 이동시키고
      • 조건에 맞게 물고기를 잡고
        • 여기서 탈출조건 확인
      • 상어를 이동시킨다.
    • 하지만 여럽지 않을것이라 생각했던 상어 이동 부분이 생각보다 복병이었다.
      • 별도의 테스트 코드와 테스트 케이스를 만들고 실험해보며 규칙성을 찾았다.
      • 노가다..
    • 전반적인 구상이 떠올랐을 때 미리 주석으로 계획을 짜 놓고 코딩하는게 훨씬 효율적이고 도움이 되었다.
  • 문제
    • https://www.acmicpc.net/problem/17143
    • 물고기 판 크기와 물고기 상태가 입력된다.
    • 낚시왕이 왼쪽끝에서 오른쪽 끝으로 가는동안 조건에 맞춰 잡을 수 있는 상어의 총 크기가 정답
      • 상어들은 매 초 속도 및 방향 조건에 따라 움직인다.
      • 낚시왕은 자기 바로 밑(같은 column)에 있는, 육지와 가장 가까운 상어 1마리만 잡을 수 있다.
      • 움직인 상어들은 가는 위치에 자신의 크기에 따라 위치하는 상어한테 잡아먹히거나 잡아먹을 수 있다.
  • 풀이
    • 우선, 입력을 받고
    • 낚시왕을 이동시키고
      • 만약 낚시왕이 탈출 조건이라면 프로그램을 끝내고
    • 이동된 위치에서 상어를 잡고
    • 상어를 이동시키는 순서대로 동작한다.
    • 자세한건 아래 코드에서 설명
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct shark
{
	int s, d, z;
};//s: 상어 속도, d: 상어 방향, z: 상어 크기

struct zips
{
	int next, dir; // 다음 위치와 방향 저장용
};

struct position
{
	int nx, ny, dir; // 다음 좌표와 방향 저장용
};

shark sharks[102][102]; // 상어 저장용
shark temp[102][102]; // 상어 이동용

int dx[] = { 0,0,0,1,-1 }; // 각각 상어의 숫자로 매핑된 이동방향
int dy[] = { 0,-1,1,0,0 };

void temp_init(int w, int h)
{ // temp 배열을 0값으로 초기화한다.
	for (int j = 1; j < h + 1; j++)
	{
		for (int i = 1; i < w + 1; i++)
		{
			temp[j][i].s = 0;
			temp[j][i].d = 0;
			temp[j][i].z = 0;
		}
	}
}

void sharks_init(int w, int h)
{
	for (int j = 1; j < h + 1; j++)
	{
		for (int i = 1; i < w + 1; i++)
		{ // shakrs 배열을 temp(계산된 값)로 초기화한다.
			sharks[j][i].s = temp[j][i].s;
			sharks[j][i].d = temp[j][i].d;
			sharks[j][i].z = temp[j][i].z;
		}
	}
}


int flip(int cd)
{ // 상어 방향 뒤집기
	if (cd == 1) return 2;
	if (cd == 3) return 4;
	if (cd == 2) return 1;
	else return 3;
}
zips next(int min, int max, int next, int dir)
{ // 다음 위치를 정하는 함수 (핵심 함수!)
	zips answer; // 정답 크기와 방향을 리턴
	while (!(min <= next && next <= max))
	{ // 상어의 다음 위치가 상어 존재 가능 위치를 벗어나는동안 while문을 돈다.
		if (next > max)
		{ // 만약 오른쪽으로 벗어났다면
			int dist = next - max; // 벗어난 길이만큼
			next = max - dist; // 다음위치를 오른쪽에서 왼쪽으로 접어준다.
			dir = flip(dir); // 방향은 뒤집어준다.
			continue; // 넘어가기
		}
		else
		{ // 만약 왼쪽으로 벗어났다면
			int dist = min - next; // 벗어난 길이만큼
			next = dist + 1; // 오른쪽으로 접어준다. 인덱스 0이 끼어있으므로 1을 더한다.
			dir = flip(dir); // 방향은 뒤집어준다 .
		}
	}
	answer.next = next; // 다음 위치 값과
	answer.dir = dir; // 다음 방향 값을
	return answer; // 반환
}

position next_position(int cx, int cy, int cd, int speed, int w, int h)
{ // 다음 위치 정하기
	int min_x = 1; // 각각 미니멈/맥시멈 값을 정하고
	int min_y = 1;
	int max_x = w;
	int max_y = h;
	
	int nd = 0; // 다음 위치 및 방향을 초기화
	int nx = cx + dx[cd] * speed;
	int ny = cy + dy[cd] * speed;

	if (cd == 1)
	{ // 위쪽 보고 있는 상어
		zips temp;
		temp = next(min_y, max_y, ny, cd); // 다음 방향과 위치를 구함
		ny = temp.next;
		nd = temp.dir;
	}
	if (cd == 3)
	{ // 오른쪽 보고 있는 상어
		zips temp;
		temp = next(min_x, max_x, nx, cd); // 다음 방향과 위치를 구함
		nx = temp.next;
		nd = temp.dir;
	}
	if (cd == 2)
	{ // 아래 보고 있는 상어
		zips temp;
		temp = next(min_y, max_y, ny, cd); // 다음 방향과 위치를 구함
		ny = temp.next;
		nd = temp.dir;
	}
	if (cd == 4)
	{ // 왼쪽 보고 있는 상어
		zips temp;
		temp = next(min_x, max_x, nx, cd); // 다음 방향과 위치를 구함
		nx = temp.next;
		nd = temp.dir;
	}

	position result;
	result.nx = nx; // 다음 위치와 방향을 리턴
	result.ny = ny;
	result.dir = nd;

	return result;
}

int main()
{
	int H, W, M; // R: 세로길이, C: 가로길이
	scanf("%d %d %d", &H, &W, &M);
	int r, c, s, d, z;

	while (M--)
	{
		scanf("%d %d %d %d %d", &r, &c, &s, &d, &z);
		sharks[r][c].s = s; // 상어를 초기화
		sharks[r][c].d = d;
		sharks[r][c].z = z;
	}

	int fisher = 0; // 낚시꾼 초기 위치
	int answer = 0;
	while (1)
	{
		fisher++; // 낚시꾼 한 칸 이동하고
		if (fisher == W + 2)
			break; //끝점이라면 빠져나온다.

		//상어 잡기
		for (int j = 1; j < H + 2; j++)
		{
			if (sharks[j][fisher].z != 0)
			{//만약 가장 가까운 칸에 상어가 있다면
				//상어 잡는다.
				answer += sharks[j][fisher].z;
				sharks[j][fisher].d = 0;
				sharks[j][fisher].s = 0;
				sharks[j][fisher].z = 0;
				break; // 잡았으면 빠져나온다.
			}
		}
		//연산용  temp 초기화
		temp_init(W, H);
		//상어 이동
		for (int j = 1; j < H + 1; j++)
		{
			for (int i = 1; i < W + 1; i++)
			{
				if (sharks[j][i].z != 0)
				{//상어가 있다면
					int cx = i;
					int cy = j;
					int cd = sharks[j][i].d; // 현재 방향
					int cz = sharks[j][i].z; // 현재 크기
					int cs = sharks[j][i].s; // 현재 속도

					//다음 좌표 구한다.
					position npos = next_position(cx, cy, cd, cs, W, H);

					//temp에 자리 이동
					if (temp[npos.ny][npos.nx].z != 0)
					{//만약 temp에 상어 미리 존재한다면
						if (temp[npos.ny][npos.nx].z < cz)
						{ // 만약 temp 존재하는 상어 크기가 현재보다 작다면 덮어쓴다
							temp[npos.ny][npos.nx].d = npos.dir;
							temp[npos.ny][npos.nx].z = cz;
							temp[npos.ny][npos.nx].s = cs;
						}
					}
					else
					{ // temp의 자리에 상어가 없다면
						temp[npos.ny][npos.nx].d = npos.dir; // 연산된 방향과 현재 크기, 속도로 초기화
						temp[npos.ny][npos.nx].z = cz;
						temp[npos.ny][npos.nx].s = cs;
					}
				}
			}
		}
    //계산된 temp맵을 상어 맵으로 최신화
		sharks_init(W, H);
	}
	printf("%d\n", answer); // 결과 출력

	//system("pause");
	return 0;
}

191007 백준 알고리즘 문제풀기

|

[3190번] 경사로

  • 난이도: 상
    • 시뮬레이션 문제로, 푸는데 2시간 이상 소요됐다. 시험에 나왔으면 망쳤을 문제다.
      • 문제 풀이 떠올리는데 1시간, 구현하면서 1시간 이상 소요
        • 문제의 조건을 정말 자세히 봐야할것 같다. 모든 조건이라도 세세하게 고려하고 판단해야 한다.
        • 문제를 너무 복잡하게 생각하다보니 자꾸 시간을 낭비하는듯 하다.
    • bfs 등 틀에 갇혀서 생각하기 때문에 더 풀기 어렵게 느껴졌던 것 같다.
      • 좀 더 유연하게 생각할 필요가 있음..
    • 또한, 행 열을 헷갈리게 써놨다. 짜증난다.
      • 열 위치인지 열의 위치인지, 행 위치인지 행의 위치인지 정확하게 조건이 구분되면 좋겟다.
        • 문제의 조건 자체가 좀 모호하게 나열되어있다.
        • 열 위치면 열 내의 위치므로 y좌표가 되는것이고
        • 열의 위치면 행에 존재하는 열의 인덱스므로 x좌표가 된다.
  • 문제
    • https://www.acmicpc.net/problem/3190
    • NxN 크기의 맵이 주어진다.
    • 사과의 개수 K와 좌표가 y, x 좌표 순으로 입력된다.
    • 방향변환 이동횟수 L과 방향변환하는 타이밍, 방향이 입력된다.
    • 전체 맵과 환경을 완성하고, 몇초동안 뱀이 움직일 수 있는지 계산해야 한다.
    • 조건
      • 맵은 몸의 길이를 우선 늘려서 다음 칸에 간다.
        • 아직 이동한것이 아님
      • 만약 다음 칸에 사과가 있으면 몸 길이를 늘린다.(1칸 늘림)
      • 만약 다음 칸에 사과가 없으면 몸 길이를 다시 수축시킨다.(1칸 당김)
      • 입력으로 주어지는 방향변환 이동횟수는 그 시간만큼 이동 후 변경하는것이 아니라 전체 시간 중 해당 타이밍에 변환하는것이다
  • 풀이
    • 전체적으로 조건이 애매해서 애매한 조건 속에서 왓다갓다 하다보니 시간이 많이 낭비되었다.
      • x, y 좌표 정의를 확실하게 하고
      • 정확하게 뱀이 어느 시점에 이동하여 해당 위치가 check 되는지
      • 방향변환이 해당 시점으로부터 그 이후인지, 처음부터 시작된 timing에서 해당 시간인지
      • 위 세 가지 조건이 명확하지 않아 엄청 시간을 날린듯 하다.
    • 문제를 나눠보면
      • 우선, 맵을 완성시킨다.
        • 맵에는 모서리 벽과 사과의 위치가 존재함
        • check 배열에는 벽의 위치만 집어넣는다.
      • 이동해야하는 순서를 moves 큐에 집어넣는다.
      • while문을 돌면서 뱀을 이동시킨다.
        • 다음 위치를 보고, 다음 위치가 접근 가능하다면 다음 위치를 snake큐에 집어넣는다.
          • snake 큐는 snake가 위치하는 좌표값들을 저장한다.
          • 만약 접근 불가능하다면 게임이 끝난것이므로 return으로 빠져나온다.
        • 다음 위치에 사과가 존재한다면
          • snake의 길이는 한 칸 길어진다. 따라서 별도의 연산이 필요 없다.
        • 다음 위치에 사과가 존재하지 않는다면
          • snake의 길이는 늘어나지 않는다. 따라서 가장 처음 들어간 값을 앞에서 뽑아준다.
            • 큐는 FIFO!
        • 만약 방향을 전환할 타이밍이라면
          • 즉, 아직 움직여야 하는 현재 시간이 움직여야 할 시간이라면
          • 방향을 전환한다.
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>
#include <deque>

using namespace std;

int map[102][102]; // 맵 저장용
int check[102][102]; // 뱀 움직임 연산용
queue<pair<int, char>> moves; // 움직임 

int answer = 0;

int dx[] = { 0,1,0,-1 }; // 각각 방향을 상 우 하 좌 를 0, 1, 2, 3으로 매핑
int dy[] = { -1,0,1,0 };

void init(int N)
{ // 맵 테두리 벽 치기
	for (int i = 0; i < N; i++)
	{
		map[0][i] = -1;
		map[N - 1][i] = -1;
		check[0][i] = -1;
		check[N - 1][i] = -1;
	}
	for (int j = 0; j < N; j++)
	{
		map[j][0] = -1;
		map[j][N - 1] = -1;
		check[j][0] = -1;
		check[j][N - 1] = -1;
	}
}
int turn_right(int cd)
{ // 우회전
	if (cd == 0) return 1;
	else if (cd == 1) return 2;
	else if (cd == 2) return 3;
	else return 0;
}
int turn_left(int cd)
{ // 좌회전
	if (cd == 0) return 3;
	else if (cd == 3) return 2;
	else if (cd == 2) return 1;
	else return 0;
}

int turn(int cd, char d)
{ // 회전시키기
	if (d == 'L')
		return turn_left(cd);
	else
		return turn_right(cd);
}

void snake_move(int x, int y, int d, int N)
{ // 뱀 움직이기
	queue<pair<int, int>> snake; // 뱀 몸 좌표 저장용
	check[y][x] = 1; // 최초 위치 초기화
	snake.push(make_pair(x, y)); // snake에 현재 좌표 넣기
	int cd = d; // 현재 방향 초기화

	int time = 0;
	
	while (1)
	{	
		time++; // 시간 증가
		int cx, cy;
		cx = snake.back().first; 현재 위치 초기화
		cy = snake.back().second;
		int nx, ny;
		nx = cx + dx[cd];
		ny = cy + dy[cd];
		if (check[ny][nx] != 0 || (nx <= 0 && N + 1 <= nx && ny <= 0 && N + 1 <= ny))
		{ // 뱀의 머리가 몸에 부딧히거나 벽이면 끝낸다.
			answer = time;
			return;
		}
		check[ny][nx] = 1; // 다음 위치가 접근 가능한경우 접근
		snake.push(make_pair(nx, ny)); // 다음 위치를 큐에 넣는다.

		if (map[ny][nx] == 1)
		{//다음에 사과가 있다면
			map[ny][nx] = 0; // 사과 먹기
		}
		else
		{//사과가 없다면
			int tx, ty;
			tx = snake.front().first;
			ty = snake.front().second; // 뱀 몸이 위치하는데서 맨 꼬리값을 반환받고
			check[ty][tx] = 0; // 꼬리칸 지운다.
			snake.pop(); // 지우기
		}

		if (!moves.empty() && moves.front().first == time)
		{//움직여야 할 경우가 남아있고, 움직일(방향전환) 시간이 되었다면
			cd = turn(cd, moves.front().second); // 방향을 전환한다.
			moves.pop(); // 방향 전환 후 이전 방향값들은 pop.
		}
	}
}

int main()
{
	//
	int N, K;
	scanf("%d", &N);
	scanf("%d", &K);
	
	init(N + 2);
	
	while (K--)
	{
		int x, y;
		scanf("%d %d", &y, &x);
		map[y][x] = 1;
	}
	int L;
	scanf("%d", &L);
	
	while (L--)
	{
		int t;
		char d;
		cin >> t;
		cin >> d;
		moves.push(make_pair(t, d));
	}

	snake_move(1, 1, 1, N);
	printf("%d\n", answer);

	//system("pause");
	return 0;
}