갬장장이
boj 6087
갬장장이
갬장장이의 코드 대장간
갬장장이
전체
오늘
어제
  • 분류 전체보기 (216)
    • 게임 연구소 (6)
    • 게임 제작 (15)
      • We need more guns (2024~) (1)
      • Rovenhell (2023) (2)
      • Geophyte (2020~2021) (5)
      • 아드레날린 러시 (2021) (2)
      • Treadmill (2019) (1)
      • 습작들 (2019~) (2)
      • 그 외 (~2018) (2)
    • mathematics (33)
      • game mathematics (30)
      • linear algebra (3)
    • networking (3)
    • computer graphics (46)
      • 3D Graphics (23)
      • DirectX (8)
      • OpenGL (13)
      • graphics theory (2)
    • game engines (10)
      • Unity (0)
      • Unreal Engine (10)
    • os (6)
      • Linux (0)
      • operating system (1)
      • multithreading, parallel co.. (5)
    • lang (34)
      • c++ (15)
      • .NET (5)
      • python (1)
      • java (3)
      • erlang, elixir (1)
      • js, ts (7)
    • software engineering (47)
      • PS (25)
      • algorithms (15)
      • data structures (2)
      • design patterns (4)
    • cs (4)
    • database (2)
      • SQL (1)
    • web (6)
      • web (3)
      • frameworks, libraries (3)
    • finance (0)
    • 음악 제작 (1)
    • life (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • [공지] 블로그 안내

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.
software engineering/PS

boj 6087

2021. 2. 7. 23:19

BFS를 사용하되, 매 루프마다 한 칸씩 이동하는 대신,

갈 수 있는 만큼 최대한 한 방향으로 이동한다.

 

또 visited 칸을 저장하는 대신, 한 번 지나간 칸에 대해 해당 칸으로 가기 까지 필요한 거울의 갯수(count)를 기록한다.

즉 count != 0 이라면 한 번 이상 방문한 칸인 셈이다.

 

BFS를 사용하기 때문에, 어느 칸에 처음 방문했을때 그 칸까지 가는 최단거리(여기서는 최소한으로 사용되는 거울 갯수)를 바로 알 수 있으며, 이러한 성질을 활용해 거울의 갯수를 축적시켜 최종적으로 목적지에 도달할때까지 길을 찾는 방식이다.

 

(굉장히 다양한 풀이가 존재하지만 이 풀이가 가장 깔끔하고 직관적인 풀이법이라고 생각한다.)

#include <iostream>
#include <queue>
using namespace std;

char grid[101][101];
int count[101][101];
int dirs[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
int W, H;
pair<int, int> start(-1,-1);
pair<int, int> goal;

void bfs() {
	queue<pair<int,int>> q;
	q.push(start);

	while (!q.empty()) {
		int currX = q.front().first;
		int currY = q.front().second;
		q.pop();

		for (auto dir : dirs) {
			int nx = currX + dir[0];
			int ny = currY + dir[1];
			while (nx >= 0 && ny >= 0 && nx < W && ny < H && grid[ny][nx] != '*') {
				if (!::count[ny][nx]) {
					::count[ny][nx] = ::count[currY][currX] + 1;
					q.push(pair<int, int>(nx, ny));
				}
				nx += dir[0]; ny += dir[1];
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	char temp;
	cin >> W >> H;

	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			cin >> temp;
			grid[i][j] = temp;
			if (temp == 'C') {
				if (start.first == -1) {
					start.first = j; start.second = i;
				}
				else {
					goal.first = j; goal.second = i;
				}
			} 
		}
	}
	bfs();
	cout << ::count[goal.second][goal.first] - 1;
}
저작자표시 비영리 변경금지 (새창열림)

'software engineering > PS' 카테고리의 다른 글

N-Queens  (0) 2021.02.23
boj 1504  (0) 2021.02.10
boj 3197  (0) 2021.01.22
0/1 Knapsack problem  (0) 2021.01.20
Stack을 활용한 Remove Adjacent Duplicates(연속된 중복 제거) 문제  (0) 2020.12.27
'software engineering/PS' 카테고리의 다른 글
  • N-Queens
  • boj 1504
  • boj 3197
  • 0/1 Knapsack problem
갬장장이
갬장장이
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.