글 읽기 - 틀린이유를 모르겠습니다. tc는 모두 통과해요

dragonite 6년 전 0

정답코드를 참조해서 수정했는데,

어디서 틀린지 모르겠습니다 ㅜㅜ

질문 검색란에 올라온 TC에 대해서는 모두 돌아갑니다.

도와주세요 ~~

/*
해당 x,y 와 k 는 재방문하지 않도록 짜여있습니다.
bfs는 visit 함수가 반드시 따라옵니다. 그렇지 않으면 무한대가 됩니다.

*/

#include <stdio.h>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

#define SIZE 55 // 51
#define qSIZE 100 // 70
char map[SIZE][SIZE];
int visit[SIZE][SIZE][1 << 7]; // 이렇게 하면 6자리 2진수가 만들어집니다.
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int n, m, startX, startY;
struct point {
	int x, y, k;
}que[qSIZE * qSIZE];
int x, y, k, nx, ny, nk;
int rear, front;
int qlen, ans;

int bfs() {
	
	// 시작하는 지점을 큐에 넣습니다.
	visit[startX][startY][0] = 1;
	rear = front = -1;
	rear++;
	que[rear].x = startX;
	que[rear].y = startY;
	que[rear].k = 0;

	while (rear != front) {
		front++;
		x = que[front].x;
		y = que[front].y;
		k = que[front].k;

		// 도착지점에 도달하면, 처음에 1로 시작했기 때문에 -1 을 해줍니다.
		if (map[x][y] == '1') return visit[x][y][k] - 1;

		// 동서남북으로 갈 수 있는 방향을 찾습니다.
		for (int i = 0; i < 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m || map[nx][ny] == '#' || visit[nx][ny][k] != 0) continue;
			
			// 키를 발견했다면, 열쇠보유상태를 갱신합니다.
			if ('a' <= map[nx][ny] && map[nx][ny] <= 'f') {
				nk = k | (1 << (map[nx][ny] - 'a')); 
				if (visit[nx][ny][nk] == 0) {
					visit[nx][ny][nk] = visit[x][y][k] + 1; // 키를 먹고, 이동합니다. 
					rear++;
					que[rear].x = nx;
					que[rear].y = ny;
					que[rear].k = nk;
				}
			}

			// 문을 발견했다면, 키를 가지고 있는지 확인한 후 이동합니다.
			else if ('A' <= map[nx][ny] && map[nx][ny] <= 'F') {
				nk = k & (1 << (map[nx][ny] - 'A')); 
				if (nk != 0) {
					visit[nx][ny][k] = visit[x][y][k] + 1;
					rear++;
					que[rear].x = nx;
					que[rear].y = ny;
					que[rear].k = k; //
				}
			}

			// 남은곳은 . 이므로 이동하면 됩니다.
			else if (visit[nx][ny][k] == 0) {
				visit[nx][ny][k] = visit[x][y][k] + 1;
				rear++;
				que[rear].x = nx;
				que[rear].y = ny;
				que[rear].k = k;
			}
		}
	}

	return -1;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> map[i];
		for (int j = 0; j < m; j++) {
			if (map[i][j] == '0') {
				startX = i;
				startY = j;
			}
		}
	}
	ans = bfs();
	cout << ans << endl;
	return 0;
}

dragonite 6년 전 1

큐사이즈를 200 으로 하니 통과되었습니다~~

rjs463 6년 전 1

시프트 연산을 어따쓰나 했더니.... 이렇게쓰는거였군뇨.. 배워갑니당.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린이유를 모르겠습니다. tc는 모두 통과해요

dragonite 6년 전 0

dragonite 6년 전 1

rjs463 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말